Gitiles
Code Review Sign In
asterix-gerrit.ics.uci.edu / incubator-asterixdb-site / 1befeb1976de14798e69b4e829c4e5b873f869fc / . / docs / 0.9.4 / sqlpp / similarity.html
blob: 6f100aee1e1370eab4be9c45e20a9f42962c1cc2 [file] [log] [blame]
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]1<!DOCTYPE html>
2<!--
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]3 | Generated by Apache Maven Doxia Site Renderer 1.8.1 from src/site/markdown/sqlpp/similarity.md at 2018-10-12
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]4 | Rendered using Apache Maven Fluido Skin 1.7
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 Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]10 <meta name="Date-Revision-yyyymmdd" content="20181012" />
Ian Maxond00eca82018-10-05 17:29:55 -0700[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.7.min.css" />
14 <link rel="stylesheet" href="../css/site.css" />
15 <link rel="stylesheet" href="../css/print.css" media="print" />
16 <script type="text/javascript" src="../js/apache-maven-fluido-1.7.min.js"></script>
17
18 </head>
19 <body class="topBarDisabled">
20 <div class="container-fluid">
21 <div id="banner">
22 <div class="pull-left"><a href=".././" id="bannerLeft"><img src="../images/asterixlogo.png" alt="AsterixDB"/></a></div>
23 <div class="pull-right"></div>
24 <div class="clear"><hr/></div>
25 </div>
26
27 <div id="breadcrumbs">
28 <ul class="breadcrumb">
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]29 <li id="publishDate">Last Published: 2018-10-12</li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]30 <li id="projectVersion" class="pull-right">Version: 0.9.4</li>
31 <li class="pull-right"><a href="../index.html" title="Documentation Home">Documentation Home</a></li>
32 </ul>
33 </div>
34 <div class="row-fluid">
35 <div id="leftColumn" class="span2">
36 <div class="well sidebar-nav">
37 <ul class="nav nav-list">
38 <li class="nav-header">Get Started - Installation</li>
39 <li><a href="../ncservice.html" title="Option 1: using NCService"><span class="none"></span>Option 1: using NCService</a></li>
40 <li><a href="../ansible.html" title="Option 2: using Ansible"><span class="none"></span>Option 2: using Ansible</a></li>
41 <li><a href="../aws.html" title="Option 3: using Amazon Web Services"><span class="none"></span>Option 3: using Amazon Web Services</a></li>
42 <li class="nav-header">AsterixDB Primer</li>
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]43 <li><a href="../sqlpp/primer-sqlpp.html" title="Using SQL++"><span class="none"></span>Using SQL++</a></li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]44 <li class="nav-header">Data Model</li>
45 <li><a href="../datamodel.html" title="The Asterix Data Model"><span class="none"></span>The Asterix Data Model</a></li>
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]46 <li class="nav-header">Queries</li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]47 <li><a href="../sqlpp/manual.html" title="The SQL++ Query Language"><span class="none"></span>The SQL++ Query Language</a></li>
48 <li><a href="../sqlpp/builtins.html" title="Builtin Functions"><span class="none"></span>Builtin Functions</a></li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]49 <li class="nav-header">API/SDK</li>
50 <li><a href="../api.html" title="HTTP API"><span class="none"></span>HTTP API</a></li>
51 <li><a href="../csv.html" title="CSV Output"><span class="none"></span>CSV Output</a></li>
52 <li class="nav-header">Advanced Features</li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]53 <li><a href="../aql/externaldata.html" title="Accessing External Data"><span class="none"></span>Accessing External Data</a></li>
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]54 <li><a href="../feeds.html" title="Data Ingestion with Feeds"><span class="none"></span>Data Ingestion with Feeds</a></li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]55 <li><a href="../udf.html" title="User Defined Functions"><span class="none"></span>User Defined Functions</a></li>
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]56 <li><a href="../sqlpp/filters.html" title="Filter-Based LSM Index Acceleration"><span class="none"></span>Filter-Based LSM Index Acceleration</a></li>
57 <li><a href="../sqlpp/fulltext.html" title="Support of Full-text Queries"><span class="none"></span>Support of Full-text Queries</a></li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]58 <li class="active"><a href="#"><span class="none"></span>Support of Similarity Queries</a></li>
Ian Maxonb2f1d3e2018-10-12 14:42:34 -0700[diff] [blame]59 <li class="nav-header">Deprecated</li>
60 <li><a href="../aql/primer.html" title="AsterixDB Primer: Using AQL"><span class="none"></span>AsterixDB Primer: Using AQL</a></li>
61 <li><a href="../aql/manual.html" title="Queries: The Asterix Query Language (AQL)"><span class="none"></span>Queries: The Asterix Query Language (AQL)</a></li>
62 <li><a href="../aql/builtins.html" title="Queries: Builtin Functions (AQL)"><span class="none"></span>Queries: Builtin Functions (AQL)</a></li>
Ian Maxond00eca82018-10-05 17:29:55 -0700[diff] [blame]63</ul>
64 <hr />
65 <div id="poweredBy">
66 <div class="clear"></div>
67 <div class="clear"></div>
68 <div class="clear"></div>
69 <div class="clear"></div>
70<a href=".././" title="AsterixDB" class="builtBy"><img class="builtBy" alt="AsterixDB" src="../images/asterixlogo.png" /></a>
71 </div>
72 </div>
73 </div>
74 <div id="bodyColumn" class="span10" >
75<!--
76 ! Licensed to the Apache Software Foundation (ASF) under one
77 ! or more contributor license agreements. See the NOTICE file
78 ! distributed with this work for additional information
79 ! regarding copyright ownership. The ASF licenses this file
80 ! to you under the Apache License, Version 2.0 (the
81 ! "License"); you may not use this file except in compliance
82 ! with the License. You may obtain a copy of the License at
83 !
84 ! http://www.apache.org/licenses/LICENSE-2.0
85 !
86 ! Unless required by applicable law or agreed to in writing,
87 ! software distributed under the License is distributed on an
88 ! "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
89 ! KIND, either express or implied. See the License for the
90 ! specific language governing permissions and limitations
91 ! under the License.
92 !-->
93<h1>AsterixDB Support of Similarity Queries</h1>
94<div class="section">
95<h2><a name="Table_of_Contents"></a><a name="toc" id="toc">Table of Contents</a></h2>
96<ul>
97
98<li><a href="#Motivation">Motivation</a></li>
99<li><a href="#DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a></li>
100<li><a href="#SimilaritySelectionQueries">Similarity Selection Queries</a></li>
101<li><a href="#SimilarityJoinQueries">Similarity Join Queries</a></li>
102<li><a href="#UsingIndexesToSupportSimilarityQueries">Using Indexes to Support Similarity Queries</a></li>
103</ul></div>
104<div class="section">
105<h2><a name="Motivation_.5BBack_to_TOC.5D"></a><a name="Motivation" id="Motivation">Motivation</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
106<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>
107<div class="section">
108<h2><a name="Data_Types_and_Similarity_Functions_.5BBack_to_TOC.5D"></a><a name="DataTypesAndSimilarityFunctions" id="DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
109<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>
110<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>
111<div class="section">
112<h2><a name="Similarity_Selection_Queries_.5BBack_to_TOC.5D"></a><a name="SimilaritySelectionQueries" id="SimilaritySelectionQueries">Similarity Selection Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
113<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>
114
115<div>
116<div>
117<pre class="source"> use dataverse TinySocial;
118
119 for $user in dataset('FacebookUsers')
120 let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
121 where $ed &lt;= 2
122 return $user
123</pre></div></div>
124
125<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>
126
127<div>
128<div>
129<pre class="source"> use dataverse TinySocial;
130
131 for $user in dataset('FacebookUsers')
132 let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
133 where $sim &gt;= 0.6f
134 return $user
135</pre></div></div>
136
137<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>
138
139<div>
140<div>
141<pre class="source"> use dataverse TinySocial;
142
143 set simfunction &quot;jaccard&quot;;
144 set simthreshold &quot;0.6f&quot;;
145
146 for $user in dataset('FacebookUsers')
147 where $user.friend-ids ~= [1,5,9,10]
148 return $user
149</pre></div></div>
150
151<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>
152<div class="section">
153<h2><a name="Similarity_Join_Queries_.5BBack_to_TOC.5D"></a><a name="SimilarityJoinQueries" id="SimilarityJoinQueries">Similarity Join Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font></h2>
154<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>
155
156<div>
157<div>
158<pre class="source"> use dataverse TinySocial;
159
160 set simfunction &quot;edit-distance&quot;;
161 set simthreshold &quot;3&quot;;
162
163 for $fbu in dataset FacebookUsers
164 return {
165 &quot;id&quot;: $fbu.id,
166 &quot;name&quot;: $fbu.name,
167 &quot;similar-users&quot;: for $t in dataset TweetMessages
168 let $tu := $t.user
169 where $tu.name ~= $fbu.name
170 return {
171 &quot;twitter-screenname&quot;: $tu.screen-name,
172 &quot;twitter-name&quot;: $tu.name
173 }
174 };
175</pre></div></div>
176</div>
177<div class="section">
178<h2><a name="Using_Indexes_to_Support_Similarity_Queries_.5BBack_to_TOC.5D"></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>
179<p>AsterixDB uses two types of indexes to support similarity queries, namely &#x201c;ngram index&#x201d; and &#x201c;keyword index&#x201d;.</p>
180<div class="section">
181<h3><a name="NGram_Index"></a>NGram Index</h3>
182<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>
183<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>
184
185<div>
186<div>
187<pre class="source"> use dataverse TinySocial;
188
189 create index fbUserIdx on FacebookUsers(name) type ngram(3);
190</pre></div></div>
191
192<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>
193<div class="section">
194<h4><a name="NGram_Index_usage_case_-_edit-distance"></a>NGram Index usage case - <a href="functions.html#edit-distance">edit-distance</a></h4>
195
196<div>
197<div>
198<pre class="source"> use dataverse TinySocial;
199
200 for $user in dataset('FacebookUsers')
201 let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
202 where $ed &lt;= 2
203 return $user
204</pre></div></div>
205</div>
206<div class="section">
207<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>
208
209<div>
210<div>
211<pre class="source"> use dataverse TinySocial;
212
213 for $user in dataset('FacebookUsers')
214 let $ed := edit-distance-check($user.name, &quot;Suzanna Tilson&quot;, 2)
215 where $ed[0]
216 return $ed[1]
217</pre></div></div>
218</div>
219<div class="section">
220<h4><a name="NGram_Index_usage_case_-_similarity-jaccard"></a>NGram Index usage case - <a href="functions.html#similarity-jaccard">similarity-jaccard</a></h4>
221
222<div>
223<div>
224<pre class="source"> use dataverse TinySocial;
225
226 for $user in dataset('FacebookUsers')
227 let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
228 where $sim &gt;= 0.6f
229 return $user
230</pre></div></div>
231</div>
232<div class="section">
233<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>
234
235<div>
236<div>
237<pre class="source"> use dataverse TinySocial;
238
239 for $user in dataset('FacebookUsers')
240 let $sim := similarity-jaccard-check($user.friend-ids, [1,5,9,10], 0.6f)
241 where $sim[0]
242 return $user
243</pre></div></div>
244</div>
245<div class="section">
246<h4><a name="NGram_Index_usage_case_-_contains.28.29"></a>NGram Index usage case - <a href="(functions.html#contains">contains()</a></h4>
247
248<div>
249<div>
250<pre class="source"> use dataverse TinySocial;
251
252 for $i in dataset('FacebookMessages')
253 where contains($i.message, &quot;phone&quot;)
254 return {&quot;mid&quot;: $i.message-id, &quot;message&quot;: $i.message}
255</pre></div></div>
256</div></div>
257<div class="section">
258<h3><a name="Keyword_Index"></a>Keyword Index</h3>
259<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>
260<div class="section">
261<h4><a name="Keyword_Index_on_String_Type"></a>Keyword Index on String Type</h4>
262
263<div>
264<div>
265<pre class="source"> use dataverse TinySocial;
266
267 drop index FacebookMessages.fbMessageIdx if exists;
268 create index fbMessageIdx on FacebookMessages(message) type keyword;
269
270 for $o in dataset('FacebookMessages')
271 let $jacc := similarity-jaccard-check(word-tokens($o.message), word-tokens(&quot;love like ccast&quot;), 0.2f)
272 where $jacc[0]
273 return $o
274</pre></div></div>
275</div>
276<div class="section">
277<h4><a name="Keyword_Index_on_UnorderedList_Type"></a>Keyword Index on UnorderedList Type</h4>
278
279<div>
280<div>
281<pre class="source"> use dataverse TinySocial;
282
283 create index fbUserIdx_fids on FacebookUsers(friend-ids) type keyword;
284
285 for $c in dataset('FacebookUsers')
286 let $jacc := similarity-jaccard-check($c.friend-ids, {{3,10}}, 0.5f)
287 where $jacc[0]
288 return $c
289</pre></div></div>
290
291<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>
292 </div>
293 </div>
294 </div>
295 <hr/>
296 <footer>
297 <div class="container-fluid">
298 <div class="row-fluid">
299<div class="row-fluid">Apache AsterixDB, AsterixDB, Apache, the Apache
300 feather logo, and the Apache AsterixDB project logo are either
301 registered trademarks or trademarks of The Apache Software
302 Foundation in the United States and other countries.
303 All other marks mentioned may be trademarks or registered
304 trademarks of their respective owners.
305 </div>
306 </div>
307 </div>
308 </footer>
309 </body>
310</html>