Gitiles
Code Review Sign In
asterix-gerrit.ics.uci.edu / incubator-asterixdb-site / d5b11d834a5431caafd6b9a551566fd7b5397168 / . / content / docs / 0.9.0 / aql / similarity.html
blob: e55d8c81a9e2d94dd54249844d1d220b802d0344 [file] [log] [blame]
Ian Maxonbf2c56b2017-01-24 14:14:49 -0800[diff] [blame]1<!DOCTYPE html>
2<!--
Ian Maxond5b11d82017-01-25 10:48:05 -0800[diff] [blame^]3 | Generated by Apache Maven Doxia at 2017-01-25
Ian Maxonbf2c56b2017-01-24 14:14:49 -0800[diff] [blame]4 | Rendered using Apache Maven Fluido Skin 1.3.0
5-->
6<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
7 <head>
8 <meta charset="UTF-8" />
9 <meta name="viewport" content="width=device-width, initial-scale=1.0" />
Ian Maxond5b11d82017-01-25 10:48:05 -0800[diff] [blame^]10 <meta name="Date-Revision-yyyymmdd" content="20170125" />
Ian Maxonbf2c56b2017-01-24 14:14:49 -0800[diff] [blame]11 <meta http-equiv="Content-Language" content="en" />
12 <title>AsterixDB &#x2013; AsterixDB Support of Similarity Queries</title>
13 <link rel="stylesheet" href="../css/apache-maven-fluido-1.3.0.min.css" />
14 <link rel="stylesheet" href="../css/site.css" />
15 <link rel="stylesheet" href="../css/print.css" media="print" />
16
17
18 <script type="text/javascript" src="../js/apache-maven-fluido-1.3.0.min.js"></script>
19
20
21
22<script>(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
23 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
24 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
25 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
26
27 ga('create', 'UA-41536543-1', 'uci.edu');
28 ga('send', 'pageview');</script>
29
30 </head>
31 <body class="topBarDisabled">
32
33
34
35
36 <div class="container-fluid">
37 <div id="banner">
38 <div class="pull-left">
39 <a href=".././" id="bannerLeft">
40 <img src="../images/asterixlogo.png" alt="AsterixDB"/>
41 </a>
42 </div>
43 <div class="pull-right"> </div>
44 <div class="clear"><hr/></div>
45 </div>
46
47 <div id="breadcrumbs">
48 <ul class="breadcrumb">
49
50
Ian Maxond5b11d82017-01-25 10:48:05 -0800[diff] [blame^]51 <li id="publishDate">Last Published: 2017-01-25</li>
Ian Maxonbf2c56b2017-01-24 14:14:49 -0800[diff] [blame]52
53
54
55 <li id="projectVersion" class="pull-right">Version: 0.9.0</li>
56
57 <li class="divider pull-right">|</li>
58
59 <li class="pull-right"> <a href="../index.html" title="Documentation Home">
60 Documentation Home</a>
61 </li>
62
63 </ul>
64 </div>
65
66
67 <div class="row-fluid">
68 <div id="leftColumn" class="span3">
69 <div class="well sidebar-nav">
70
71
72 <ul class="nav nav-list">
73 <li class="nav-header">Get Started - Installation</li>
74
75 <li>
76
77 <a href="../ncservice.html" title="Option 1: using NCService">
78 <i class="none"></i>
79 Option 1: using NCService</a>
80 </li>
81
82 <li>
83
84 <a href="../install.html" title="Option 2: using Managix">
85 <i class="none"></i>
86 Option 2: using Managix</a>
87 </li>
88
89 <li>
90
91 <a href="../yarn.html" title="Option 3: using YARN">
92 <i class="none"></i>
93 Option 3: using YARN</a>
94 </li>
95 <li class="nav-header">AsterixDB Primer</li>
96
97 <li>
98
99 <a href="../sqlpp/primer-sqlpp.html" title="Option 1: using SQL++">
100 <i class="none"></i>
101 Option 1: using SQL++</a>
102 </li>
103
104 <li>
105
106 <a href="../aql/primer.html" title="Option 2: using AQL">
107 <i class="none"></i>
108 Option 2: using AQL</a>
109 </li>
110 <li class="nav-header">Data Model</li>
111
112 <li>
113
114 <a href="../datamodel.html" title="The Asterix Data Model">
115 <i class="none"></i>
116 The Asterix Data Model</a>
117 </li>
118 <li class="nav-header">Queries - SQL++</li>
119
120 <li>
121
122 <a href="../sqlpp/manual.html" title="The SQL++ Query Language">
123 <i class="none"></i>
124 The SQL++ Query Language</a>
125 </li>
126
127 <li>
128
129 <a href="../sqlpp/builtins.html" title="Builtin Functions">
130 <i class="none"></i>
131 Builtin Functions</a>
132 </li>
133 <li class="nav-header">Queries - AQL</li>
134
135 <li>
136
137 <a href="../aql/manual.html" title="The Asterix Query Language (AQL)">
138 <i class="none"></i>
139 The Asterix Query Language (AQL)</a>
140 </li>
141
142 <li>
143
144 <a href="../aql/builtins.html" title="Builtin Functions">
145 <i class="none"></i>
146 Builtin Functions</a>
147 </li>
148 <li class="nav-header">Advanced Features</li>
149
150 <li class="active">
151
152 <a href="#"><i class="none"></i>Support of Similarity Queries</a>
153 </li>
154
155 <li>
156
157 <a href="../aql/fulltext.html" title="Support of Full-text Queries">
158 <i class="none"></i>
159 Support of Full-text Queries</a>
160 </li>
161
162 <li>
163
164 <a href="../aql/externaldata.html" title="Accessing External Data">
165 <i class="none"></i>
166 Accessing External Data</a>
167 </li>
168
169 <li>
170
171 <a href="../feeds/tutorial.html" title="Support for Data Ingestion">
172 <i class="none"></i>
173 Support for Data Ingestion</a>
174 </li>
175
176 <li>
177
178 <a href="../udf.html" title="User Defined Functions">
179 <i class="none"></i>
180 User Defined Functions</a>
181 </li>
182
183 <li>
184
185 <a href="../aql/filters.html" title="Filter-Based LSM Index Acceleration">
186 <i class="none"></i>
187 Filter-Based LSM Index Acceleration</a>
188 </li>
189 <li class="nav-header">API/SDK</li>
190
191 <li>
192
193 <a href="../api.html" title="HTTP API">
194 <i class="none"></i>
195 HTTP API</a>
196 </li>
197 </ul>
198
199
200
201 <hr class="divider" />
202
203 <div id="poweredBy">
204 <div class="clear"></div>
205 <div class="clear"></div>
206 <div class="clear"></div>
207 <a href=".././" title="AsterixDB" class="builtBy">
208 <img class="builtBy" alt="AsterixDB" src="../images/asterixlogo.png" />
209 </a>
210 </div>
211 </div>
212 </div>
213
214
215 <div id="bodyColumn" class="span9" >
216
217 <!-- ! Licensed to the Apache Software Foundation (ASF) under one
218 ! or more contributor license agreements. See the NOTICE file
219 ! distributed with this work for additional information
220 ! regarding copyright ownership. The ASF licenses this file
221 ! to you under the Apache License, Version 2.0 (the
222 ! "License"); you may not use this file except in compliance
223 ! with the License. You may obtain a copy of the License at
224 !
225 ! http://www.apache.org/licenses/LICENSE-2.0
226 !
227 ! Unless required by applicable law or agreed to in writing,
228 ! software distributed under the License is distributed on an
229 ! "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
230 ! KIND, either express or implied. See the License for the
231 ! specific language governing permissions and limitations
232 ! under the License.
233 ! --><h1>AsterixDB Support of Similarity Queries</h1>
234<div class="section">
235<h2><a name="Table_of_Contents"></a><a name="toc" id="toc">Table of Contents</a></h2>
236
237<ul>
238
239<li><a href="#Motivation">Motivation</a></li>
240
241<li><a href="#DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a></li>
242
243<li><a href="#SimilaritySelectionQueries">Similarity Selection Queries</a></li>
244
245<li><a href="#SimilarityJoinQueries">Similarity Join Queries</a></li>
246
247<li><a href="#UsingIndexesToSupportSimilarityQueries">Using Indexes to Support Similarity Queries</a></li>
248</ul></div>
249<div class="section">
250<h2><a name="Motivation_Back_to_TOC"></a><a name="Motivation" id="Motivation">Motivation</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
251<p>Similarity queries are widely used in applications where users need to find objects that satisfy a similarity predicate, while exact matching is not sufficient. These queries are especially important for social and Web applications, where errors, abbreviations, and inconsistencies are common. As an example, we may want to find all the movies starring Schwarzenegger, while we don&#x2019;t know the exact spelling of his last name (despite his popularity in both the movie industry and politics :-)). As another example, we want to find all the Facebook users who have similar friends. To meet this type of needs, AsterixDB supports similarity queries using efficient indexes and algorithms.</p></div>
252<div class="section">
253<h2><a name="Data_Types_and_Similarity_Functions_Back_to_TOC"></a><a name="DataTypesAndSimilarityFunctions" id="DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
254<p>AsterixDB supports <a class="externalLink" href="http://en.wikipedia.org/wiki/Levenshtein_distance">edit distance</a> (on strings) and <a class="externalLink" href="http://en.wikipedia.org/wiki/Jaccard_index">Jaccard</a> (on sets). For instance, in our <a href="primer.html#ADM:_Modeling_Semistructed_Data_in_AsterixDB">TinySocial</a> example, the <tt>friend-ids</tt> of a Facebook user forms a set of friends, and we can define a similarity between the sets of friends of two users. We can also convert a string to a set of grams of a length &#x201c;n&#x201d; (called &#x201c;n-grams&#x201d;) and define the Jaccard similarity between the two gram sets of the two strings. Formally, the &#x201c;n-grams&#x201d; of a string are its substrings of length &#x201c;n&#x201d;. For instance, the 3-grams of the string <tt>schwarzenegger</tt> are <tt>sch</tt>, <tt>chw</tt>, <tt>hwa</tt>, &#x2026;, <tt>ger</tt>.</p>
255<p>AsterixDB provides <a href="functions.html#Tokenizing_Functions">tokenization functions</a> to convert strings to sets, and the <a href="functions.html#Similarity_Functions">similarity functions</a>.</p></div>
256<div class="section">
257<h2><a name="Similarity_Selection_Queries_Back_to_TOC"></a><a name="SimilaritySelectionQueries" id="SimilaritySelectionQueries">Similarity Selection Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
258<p>The following query asks for all the Facebook users whose name is similar to <tt>Suzanna Tilson</tt>, i.e., their edit distance is at most 2.</p>
259
260<div class="source">
261<div class="source">
262<pre> use dataverse TinySocial;
263
264 for $user in dataset('FacebookUsers')
265 let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
266 where $ed &lt;= 2
267 return $user
268</pre></div></div>
269<p>The following query asks for all the Facebook users whose set of friend ids is similar to <tt>[1,5,9,10]</tt>, i.e., their Jaccard similarity is at least 0.6.</p>
270
271<div class="source">
272<div class="source">
273<pre> use dataverse TinySocial;
274
275 for $user in dataset('FacebookUsers')
276 let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
277 where $sim &gt;= 0.6f
278 return $user
279</pre></div></div>
280<p>AsterixDB allows a user to use a similarity operator <tt>~=</tt> to express a condition by defining the similarity function and threshold using &#x201c;set&#x201d; statements earlier. For instance, the above query can be equivalently written as:</p>
281
282<div class="source">
283<div class="source">
284<pre> use dataverse TinySocial;
285
286 set simfunction &quot;jaccard&quot;;
287 set simthreshold &quot;0.6f&quot;;
288
289 for $user in dataset('FacebookUsers')
290 where $user.friend-ids ~= [1,5,9,10]
291 return $user
292</pre></div></div>
293<p>In this query, we first declare Jaccard as the similarity function using <tt>simfunction</tt> and then specify the threshold <tt>0.6f</tt> using <tt>simthreshold</tt>.</p></div>
294<div class="section">
295<h2><a name="Similarity_Join_Queries_Back_to_TOC"></a><a name="SimilarityJoinQueries" id="SimilarityJoinQueries">Similarity Join Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
296<p>AsterixDB supports fuzzy joins between two sets. The following <a href="primer.html#Query_5_-_Fuzzy_Join">query</a> finds, for each Facebook user, all Twitter users with names similar to their name based on the edit distance.</p>
297
298<div class="source">
299<div class="source">
300<pre> use dataverse TinySocial;
301
302 set simfunction &quot;edit-distance&quot;;
303 set simthreshold &quot;3&quot;;
304
305 for $fbu in dataset FacebookUsers
306 return {
307 &quot;id&quot;: $fbu.id,
308 &quot;name&quot;: $fbu.name,
309 &quot;similar-users&quot;: for $t in dataset TweetMessages
310 let $tu := $t.user
311 where $tu.name ~= $fbu.name
312 return {
313 &quot;twitter-screenname&quot;: $tu.screen-name,
314 &quot;twitter-name&quot;: $tu.name
315 }
316 };
317</pre></div></div></div>
318<div class="section">
319<h2><a name="Using_Indexes_to_Support_Similarity_Queries_Back_to_TOC"></a><a name="UsingIndexesToSupportSimilarityQueries" id="UsingIndexesToSupportSimilarityQueries">Using Indexes to Support Similarity Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
320<p>AsterixDB uses two types of indexes to support similarity queries, namely &#x201c;ngram index&#x201d; and &#x201c;keyword index&#x201d;.</p>
321<div class="section">
322<h3><a name="NGram_Index"></a>NGram Index</h3>
323<p>An &#x201c;ngram index&#x201d; is constructed on a set of strings. We generate n-grams for each string, and build an inverted list for each n-gram that includes the ids of the strings with this gram. A similarity query can be answered efficiently by accessing the inverted lists of the grams in the query and counting the number of occurrences of the string ids on these inverted lists. The similar idea can be used to answer queries with Jaccard similarity. A detailed description of these techniques is available at this <a class="externalLink" href="http://www.ics.uci.edu/~chenli/pub/icde2009-memreducer.pdf">paper</a>.</p>
324<p>For instance, the following DDL statements create an ngram index on the <tt>FacebookUsers.name</tt> attribute using an inverted index of 3-grams.</p>
325
326<div class="source">
327<div class="source">
328<pre> use dataverse TinySocial;
329
330 create index fbUserIdx on FacebookUsers(name) type ngram(3);
331</pre></div></div>
332<p>The number &#x201c;3&#x201d; in &#x201c;ngram(3)&#x201d; is the length &#x201c;n&#x201d; in the grams. This index can be used to optimize similarity queries on this attribute using <a href="functions.html#edit-distance">edit-distance</a>, <a href="functions.html#edit-distance-check">edit-distance-check</a>, <a href="functions.html#similarity-jaccard">similarity-jaccard</a>, or <a href="functions.html#similarity-jaccard-check">similarity-jaccard-check</a> queries on this attribute where the similarity is defined on sets of 3-grams. This index can also be used to optimize queries with the &#x201c;<a href="functions.html#contains">contains()</a>&#x201d; predicate (i.e., substring matching) since it can be also be solved by counting on the inverted lists of the grams in the query string.</p>
333<div class="section">
334<h4><a name="NGram_Index_usage_case_-_edit-distance"></a>NGram Index usage case - <a href="functions.html#edit-distance">edit-distance</a></h4>
335
336<div class="source">
337<div class="source">
338<pre> use dataverse TinySocial;
339
340 for $user in dataset('FacebookUsers')
341 let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
342 where $ed &lt;= 2
343 return $user
344</pre></div></div></div>
345<div class="section">
346<h4><a name="NGram_Index_usage_case_-_edit-distance-check"></a>NGram Index usage case - <a href="functions.html#edit-distance-check">edit-distance-check</a></h4>
347
348<div class="source">
349<div class="source">
350<pre> use dataverse TinySocial;
351
352 for $user in dataset('FacebookUsers')
353 let $ed := edit-distance-check($user.name, &quot;Suzanna Tilson&quot;, 2)
354 where $ed[0]
355 return $ed[1]
356</pre></div></div></div>
357<div class="section">
358<h4><a name="NGram_Index_usage_case_-_similarity-jaccard"></a>NGram Index usage case - <a href="functions.html#similarity-jaccard">similarity-jaccard</a></h4>
359
360<div class="source">
361<div class="source">
362<pre> use dataverse TinySocial;
363
364 for $user in dataset('FacebookUsers')
365 let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
366 where $sim &gt;= 0.6f
367 return $user
368</pre></div></div></div>
369<div class="section">
370<h4><a name="NGram_Index_usage_case_-_similarity-jaccard-check"></a>NGram Index usage case - <a href="functions.html#similarity-jaccard-check">similarity-jaccard-check</a></h4>
371
372<div class="source">
373<div class="source">
374<pre> use dataverse TinySocial;
375
376 for $user in dataset('FacebookUsers')
377 let $sim := similarity-jaccard-check($user.friend-ids, [1,5,9,10], 0.6f)
378 where $sim[0]
379 return $user
380</pre></div></div></div>
381<div class="section">
382<h4><a name="NGram_Index_usage_case_-_contains"></a>NGram Index usage case - <a href="functions.html#contains">contains()</a></h4>
383
384<div class="source">
385<div class="source">
386<pre> use dataverse TinySocial;
387
388 for $i in dataset('FacebookMessages')
389 where contains($i.message, &quot;phone&quot;)
390 return {&quot;mid&quot;: $i.message-id, &quot;message&quot;: $i.message}
391</pre></div></div></div></div>
392<div class="section">
393<h3><a name="Keyword_Index"></a>Keyword Index</h3>
394<p>A &#x201c;keyword index&#x201d; is constructed on a set of strings or sets (e.g., OrderedList, UnorderedList). Instead of generating grams as in an ngram index, we generate tokens (e.g., words) and for each token, construct an inverted list that includes the ids of the objects with this token. The following two examples show how to create keyword index on two different types:</p>
395<div class="section">
396<h4><a name="Keyword_Index_on_String_Type"></a>Keyword Index on String Type</h4>
397
398<div class="source">
399<div class="source">
400<pre> use dataverse TinySocial;
401
402 drop index FacebookMessages.fbMessageIdx if exists;
403 create index fbMessageIdx on FacebookMessages(message) type keyword;
404
405 for $o in dataset('FacebookMessages')
406 let $jacc := similarity-jaccard-check(word-tokens($o.message), word-tokens(&quot;love like verizon&quot;), 0.2f)
407 where $jacc[0]
408 return $o
409</pre></div></div></div>
410<div class="section">
411<h4><a name="Keyword_Index_on_UnorderedList_Type"></a>Keyword Index on UnorderedList Type</h4>
412
413<div class="source">
414<div class="source">
415<pre> use dataverse TinySocial;
416
417 create index fbUserIdx_fids on FacebookUsers(friend-ids) type keyword;
418
419 for $c in dataset('FacebookUsers')
420 let $jacc := similarity-jaccard-check($c.friend-ids, {{3,10}}, 0.5f)
421 where $jacc[0]
422 return $c
423</pre></div></div>
424<p>As shown above, keyword index can be used to optimize queries with token-based similarity predicates, including <a href="functions.html#similarity-jaccard">similarity-jaccard</a> and <a href="functions.html#similarity-jaccard-check">similarity-jaccard-check</a>.</p></div></div></div>
425 </div>
426 </div>
427 </div>
428
429 <hr/>
430
431 <footer>
432 <div class="container-fluid">
433 <div class="row span12">Copyright &copy; 2017
434 <a href="https://www.apache.org/">The Apache Software Foundation</a>.
435 All Rights Reserved.
436
437 </div>
438
439 <?xml version="1.0" encoding="UTF-8"?>
440<div class="row-fluid">Apache AsterixDB, AsterixDB, Apache, the Apache
441 feather logo, and the Apache AsterixDB project logo are either
442 registered trademarks or trademarks of The Apache Software
443 Foundation in the United States and other countries.
444 All other marks mentioned may be trademarks or registered
445 trademarks of their respective owners.</div>
446
447
448 </div>
449 </footer>
450 </body>
451</html>