Gitiles
Code Review Sign In
asterix-gerrit.ics.uci.edu / incubator-asterixdb-site / b57cd730819d63cbf244c7c2d1b19bc9b91ba099 / . / content / docs / 0.9.9 / sqlpp / similarity.html
blob: fbc63700cc1ce16c4ce6a349ab5e6644d6d4bc52 [file] [log] [blame]
Ian Maxonbf8620b2024-04-01 16:09:18 -0700[diff] [blame]1<!DOCTYPE html>
2<!--
3 | Generated by Apache Maven Doxia Site Renderer 1.8.1 from src/site/markdown/sqlpp/similarity.md at 2024-04-01
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" />
10 <meta name="Date-Revision-yyyymmdd" content="20240401" />
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">
29 <li id="publishDate">Last Published: 2024-04-01</li>
30 <li id="projectVersion" class="pull-right">Version: 0.9.9</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>
43 <li><a href="../sqlpp/primer-sqlpp.html" title="Using SQL++"><span class="none"></span>Using SQL++</a></li>
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>
46 <li class="nav-header">Queries</li>
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.html" title="Raw SQL++ Grammar"><span class="none"></span>Raw SQL++ Grammar</a></li>
49 <li><a href="../sqlpp/builtins.html" title="Builtin Functions"><span class="none"></span>Builtin Functions</a></li>
50 <li class="nav-header">API/SDK</li>
51 <li><a href="../api.html" title="HTTP API"><span class="none"></span>HTTP API</a></li>
52 <li><a href="../csv.html" title="CSV Output"><span class="none"></span>CSV Output</a></li>
53 <li class="nav-header">Advanced Features</li>
54 <li><a href="../aql/externaldata.html" title="Accessing External Data"><span class="none"></span>Accessing External Data</a></li>
55 <li><a href="../feeds.html" title="Data Ingestion with Feeds"><span class="none"></span>Data Ingestion with Feeds</a></li>
56 <li><a href="../udf.html" title="User Defined Functions"><span class="none"></span>User Defined Functions</a></li>
57 <li><a href="../sqlpp/filters.html" title="Filter-Based LSM Index Acceleration"><span class="none"></span>Filter-Based LSM Index Acceleration</a></li>
58 <li><a href="../sqlpp/fulltext.html" title="Support of Full-text Queries"><span class="none"></span>Support of Full-text Queries</a></li>
59 <li class="active"><a href="#"><span class="none"></span>Support of Similarity Queries</a></li>
60 <li><a href="../geo/quickstart.html" title="GIS Support Overview"><span class="none"></span>GIS Support Overview</a></li>
61 <li><a href="../geo/functions.html" title="GIS Functions"><span class="none"></span>GIS Functions</a></li>
62 <li><a href="../interval_join.html" title="Support of Interval Joins"><span class="none"></span>Support of Interval Joins</a></li>
63 <li><a href="../spatial_join.html" title="Support of Spatial Joins"><span class="none"></span>Support of Spatial Joins</a></li>
64 <li><a href="../sqlpp/arrayindex.html" title="Support of Array Indexes"><span class="none"></span>Support of Array Indexes</a></li>
65 <li class="nav-header">Deprecated</li>
66 <li><a href="../aql/primer.html" title="AsterixDB Primer: Using AQL"><span class="none"></span>AsterixDB Primer: Using AQL</a></li>
67 <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>
68 <li><a href="../aql/builtins.html" title="Queries: Builtin Functions (AQL)"><span class="none"></span>Queries: Builtin Functions (AQL)</a></li>
69</ul>
70 <hr />
71 <div id="poweredBy">
72 <div class="clear"></div>
73 <div class="clear"></div>
74 <div class="clear"></div>
75 <div class="clear"></div>
76<a href=".././" title="AsterixDB" class="builtBy"><img class="builtBy" alt="AsterixDB" src="../images/asterixlogo.png" /></a>
77 </div>
78 </div>
79 </div>
80 <div id="bodyColumn" class="span10" >
81<!--
82 ! Licensed to the Apache Software Foundation (ASF) under one
83 ! or more contributor license agreements. See the NOTICE file
84 ! distributed with this work for additional information
85 ! regarding copyright ownership. The ASF licenses this file
86 ! to you under the Apache License, Version 2.0 (the
87 ! "License"); you may not use this file except in compliance
88 ! with the License. You may obtain a copy of the License at
89 !
90 ! http://www.apache.org/licenses/LICENSE-2.0
91 !
92 ! Unless required by applicable law or agreed to in writing,
93 ! software distributed under the License is distributed on an
94 ! "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
95 ! KIND, either express or implied. See the License for the
96 ! specific language governing permissions and limitations
97 ! under the License.
98 !-->
99<h1>AsterixDB Support of Similarity Queries</h1>
100<div class="section">
101<h2><a name="Table_of_Contents"></a><a name="toc" id="toc">Table of Contents</a></h2>
102<ul>
103
104<li><a href="#Motivation">Motivation</a></li>
105<li><a href="#DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a></li>
106<li><a href="#SimilaritySelectionQueries">Similarity Selection Queries</a></li>
107<li><a href="#SimilarityJoinQueries">Similarity Join Queries</a></li>
108<li><a href="#UsingIndexesToSupportSimilarityQueries">Using Indexes to Support Similarity Queries</a></li>
109</ul></div>
110<div class="section">
111<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>
112<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>
113<div class="section">
114<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>
115<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="../sqlpp/primer-sqlpp.html#ADM:_Modeling_Semistructured_Data_in_AsterixDB">TinySocial</a> example, the <tt>friendIds</tt> of a Gleambook 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>
116<p>AsterixDB provides <a href="../sqlpp/builtins.html#Tokenizing_Functions">tokenization functions</a> to convert strings to sets, and the <a href="../sqlpp/builtins.html#Similarity_Functions">similarity functions</a>.</p></div>
117<div class="section">
118<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>
119<p>The following query asks for all the Gleambook users whose name is similar to <tt>Suzanna Tilson</tt>, i.e., their edit distance is at most 2.</p>
120
121<div>
122<div>
123<pre class="source"> use TinySocial;
124
125 select u
126 from GleambookUsers u
127 where edit_distance(u.name, &quot;Suzanna Tilson&quot;) &lt;= 2;
128</pre></div></div>
129
130<p>The following query asks for all the Gleambook 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>
131
132<div>
133<div>
134<pre class="source"> use TinySocial;
135
136 select u
137 from GleambookUsers u
138 where similarity_jaccard(u.friendIds, [1,5,9,10]) &gt;= 0.6f;
139</pre></div></div>
140
141<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>
142
143<div>
144<div>
145<pre class="source"> use TinySocial;
146
147 set simfunction &quot;jaccard&quot;;
148 set simthreshold &quot;0.6f&quot;;
149
150 select u
151 from GleambookUsers u
152 where u.friendIds ~= [1,5,9,10];
153</pre></div></div>
154
155<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>
156<div class="section">
157<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>
158<p>AsterixDB supports fuzzy joins between two sets. The following <a href="../sqlpp/primer-sqlpp.html#Query_5_-_Fuzzy_Join">query</a> finds, for each Gleambook user, all Chirp users with names similar to their name based on the edit distance.</p>
159
160<div>
161<div>
162<pre class="source"> use TinySocial;
163
164 set simfunction &quot;edit-distance&quot;;
165 set simthreshold &quot;3&quot;;
166
167 select gbu.id, gbu.name, (select cu.screenName, cu.name
168 from ChirpUsers cu
169 where cu.name ~= gbu.name) as similar_users
170 from GleambookUsers gbu;
171</pre></div></div>
172</div>
173<div class="section">
174<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>
175<p>AsterixDB uses two types of indexes to support similarity queries, namely &#x201c;ngram index&#x201d; and &#x201c;keyword index&#x201d;.</p>
176<div class="section">
177<h3><a name="NGram_Index"></a>NGram Index</h3>
178<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>
179<p>For instance, the following DDL statements create an ngram index on the <tt>GleambookUsers.name</tt> attribute using an inverted index of 3-grams.</p>
180
181<div>
182<div>
183<pre class="source"> use TinySocial;
184
185 create index gbUserIdx on GleambookUsers(name) type ngram(3);
186</pre></div></div>
187
188<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="../sqlpp/builtins.html#edit_distance">edit_distance</a>, <a href="../sqlpp/builtins.html#edit_distance_check">edit_distance_check</a>, <a href="../sqlpp/builtins.html#similarity_jaccard">similarity_jaccard</a>, or <a href="../sqlpp/builtins.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="(../sqlpp/builtins.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>
189<div class="section">
190<h4><a name="NGram_Index_usage_case_-_edit_distance"></a>NGram Index usage case - <a href="../sqlpp/builtins.html#edit-distance">edit_distance</a></h4>
191
192<div>
193<div>
194<pre class="source"> use TinySocial;
195
196 select u
197 from GleambookUsers u
198 where edit_distance(u.name, &quot;Suzanna Tilson&quot;) &lt;= 2;
199</pre></div></div>
200</div>
201<div class="section">
202<h4><a name="NGram_Index_usage_case_-_edit_distance_check"></a>NGram Index usage case - <a href="../sqlpp/builtins.html#edit_distance_check">edit_distance_check</a></h4>
203
204<div>
205<div>
206<pre class="source"> use TinySocial;
207
208 select u
209 from GleambookUsers u
210 where edit_distance_check(u.name, &quot;Suzanna Tilson&quot;, 2)[0];
211</pre></div></div>
212</div>
213<div class="section">
214<h4><a name="NGram_Index_usage_case_-_contains.28.29"></a>NGram Index usage case - <a href="(../sqlpp/builtins.html#contains">contains()</a></h4>
215
216<div>
217<div>
218<pre class="source"> use TinySocial;
219
220 select m
221 from GleambookMessages m
222 where contains(m.message, &quot;phone&quot;);
223</pre></div></div>
224</div></div>
225<div class="section">
226<h3><a name="Keyword_Index"></a>Keyword Index</h3>
227<p>A &#x201c;keyword index&#x201d; is constructed on a set of strings or sets (e.g., array, multiset). 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>
228<div class="section">
229<h4><a name="Keyword_Index_on_String_Type"></a>Keyword Index on String Type</h4>
230
231<div>
232<div>
233<pre class="source"> use TinySocial;
234
235 drop index GleambookMessages.gbMessageIdx if exists;
236 create index gbMessageIdx on GleambookMessages(message) type keyword;
237
238 select m
239 from GleambookMessages m
240 where similarity_jaccard_check(word_tokens(m.message), word_tokens(&quot;love like ccast&quot;), 0.2f)[0];
241</pre></div></div>
242</div>
243<div class="section">
244<h4><a name="Keyword_Index_on_Multiset_Type"></a>Keyword Index on Multiset Type</h4>
245
246<div>
247<div>
248<pre class="source"> use TinySocial;
249
250 create index gbUserIdxFIds on GleambookUsers(friendIds) type keyword;
251
252 select u
253 from GleambookUsers u
254 where similarity_jaccard_check(u.friendIds, {{3,10}}, 0.5f)[0];
255</pre></div></div>
256
257<p>As shown above, keyword index can be used to optimize queries with token-based similarity predicates, including <a href="../sqlpp/builtins.html#similarity_jaccard">similarity_jaccard</a> and <a href="../sqlpp/builtins.html#similarity_jaccard_check">similarity_jaccard_check</a>.</p></div>
258<div class="section">
259<h4><a name="Keyword_Index_usage_case_-_similarity_jaccard"></a>Keyword Index usage case - <a href="../sqlpp/builtins.html#similarity_jaccard">similarity_jaccard</a></h4>
260
261<div>
262<div>
263<pre class="source"> use TinySocial;
264
265 select u
266 from GleambookUsers u
267 where similarity_jaccard(u.friendIds, [1,5,9,10]) &gt;= 0.6f;
268</pre></div></div>
269</div>
270<div class="section">
271<h4><a name="Keyword_Index_usage_case_-_similarity_jaccard_check"></a>Keyword Index usage case - <a href="../sqlpp/builtins.html#similarity_jaccard_check">similarity_jaccard_check</a></h4>
272
273<div>
274<div>
275<pre class="source"> use TinySocial;
276
277 select u
278 from GleambookUsers u
279 where similarity_jaccard_check(u.friendIds, [1,5,9,10], 0.6f)[0];
280</pre></div></div></div></div></div>
281 </div>
282 </div>
283 </div>
284 <hr/>
285 <footer>
286 <div class="container-fluid">
287 <div class="row-fluid">
288<div class="row-fluid">Apache AsterixDB, AsterixDB, Apache, the Apache
289 feather logo, and the Apache AsterixDB project logo are either
290 registered trademarks or trademarks of The Apache Software
291 Foundation in the United States and other countries.
292 All other marks mentioned may be trademarks or registered
293 trademarks of their respective owners.
294 </div>
295 </div>
296 </div>
297 </footer>
298 </body>
299</html>