asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [08/30] incubator-asterixdb-site git commit: Include stable docs, use Apache URLs
Date Wed, 25 Nov 2015 19:30:07 GMT
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-site/blob/e2b799e7/docs/0.8.7-incubating/aql/similarity.html
----------------------------------------------------------------------
diff --git a/docs/0.8.7-incubating/aql/similarity.html b/docs/0.8.7-incubating/aql/similarity.html
new file mode 100644
index 0000000..ce239aa
--- /dev/null
+++ b/docs/0.8.7-incubating/aql/similarity.html
@@ -0,0 +1,431 @@
+<!DOCTYPE html>
+<!--
+ | Generated by Apache Maven Doxia at 2015-11-24
+ | Rendered using Apache Maven Fluido Skin 1.3.0
+-->
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
+  <head>
+    <meta charset="UTF-8" />
+    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
+    <meta name="Date-Revision-yyyymmdd" content="20151124" />
+    <meta http-equiv="Content-Language" content="en" />
+    <title>AsterixDB &#x2013; AsterixDB Support of Similarity Queries</title>
+    <link rel="stylesheet" href="../css/apache-maven-fluido-1.3.0.min.css" />
+    <link rel="stylesheet" href="../css/site.css" />
+    <link rel="stylesheet" href="../css/print.css" media="print" />
+
+      
+    <script type="text/javascript" src="../js/apache-maven-fluido-1.3.0.min.js"></script>
+
+                          
+        
+<script>(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+        })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+
+        ga('create', 'UA-41536543-1', 'uci.edu');
+        ga('send', 'pageview');</script>
+          
+            </head>
+        <body class="topBarDisabled">
+          
+                
+                    
+    
+        <div class="container-fluid">
+          <div id="banner">
+        <div class="pull-left">
+                                    <a href="http://asterixdb.apache.org/" id="bannerLeft">
+                                                                                        
       <img src="../images/asterixlogo.png"  alt="AsterixDB"/>
+                </a>
+                      </div>
+        <div class="pull-right">  </div>
+        <div class="clear"><hr/></div>
+      </div>
+
+      <div id="breadcrumbs">
+        <ul class="breadcrumb">
+                
+                    
+                  <li id="publishDate">Last Published: 2015-11-24</li>
+                      
+                
+                    
+                 <li id="projectVersion" class="pull-right">Version: 0.8.7-incubating</li>
+      
+                                            <li class="divider pull-right">|</li>
+                        
+    <li class="pull-right">              <a href="../index.html" title="Documentation
Home">
+        Documentation Home</a>
+  </li>
+
+                        </ul>
+      </div>
+
+            
+      <div class="row-fluid">
+        <div id="leftColumn" class="span3">
+          <div class="well sidebar-nav">
+                
+                    
+                <ul class="nav nav-list">
+                    <li class="nav-header">Documentation</li>
+                                
+      <li>
+    
+                          <a href="../install.html" title="Installing and Managing AsterixDB
using Managix">
+          <i class="none"></i>
+        Installing and Managing AsterixDB using Managix</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../yarn.html" title="Deploying AsterixDB using YARN">
+          <i class="none"></i>
+        Deploying AsterixDB using YARN</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/primer.html" title="AsterixDB 101: An ADM and
AQL Primer">
+          <i class="none"></i>
+        AsterixDB 101: An ADM and AQL Primer</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/primer-sql-like.html" title="AsterixDB 101:
An ADM and AQL Primer (For SQL Fans)">
+          <i class="none"></i>
+        AsterixDB 101: An ADM and AQL Primer (For SQL Fans)</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/js-sdk.html" title="AsterixDB Javascript SDK">
+          <i class="none"></i>
+        AsterixDB Javascript SDK</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/datamodel.html" title="Asterix Data Model (ADM)">
+          <i class="none"></i>
+        Asterix Data Model (ADM)</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/manual.html" title="Asterix Query Language (AQL)">
+          <i class="none"></i>
+        Asterix Query Language (AQL)</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/functions.html" title="AQL Functions">
+          <i class="none"></i>
+        AQL Functions</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/allens.html" title="AQL Allen's Relations Functions">
+          <i class="none"></i>
+        AQL Allen's Relations Functions</a>
+            </li>
+                  
+      <li class="active">
+    
+            <a href="#"><i class="none"></i>AQL Support of Similarity Queries</a>
+          </li>
+                  
+      <li>
+    
+                          <a href="../aql/externaldata.html" title="Accessing External
Data">
+          <i class="none"></i>
+        Accessing External Data</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../feeds/tutorial.html" title="Support for Data Ingestion
in AsterixDB">
+          <i class="none"></i>
+        Support for Data Ingestion in AsterixDB</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../udf.html" title="Support for User Defined Functions
in AsterixDB">
+          <i class="none"></i>
+        Support for User Defined Functions in AsterixDB</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../aql/filters.html" title="Filter-Based LSM Index
Acceleration">
+          <i class="none"></i>
+        Filter-Based LSM Index Acceleration</a>
+            </li>
+                  
+      <li>
+    
+                          <a href="../api.html" title="HTTP API to AsterixDB">
+          <i class="none"></i>
+        HTTP API to AsterixDB</a>
+            </li>
+            </ul>
+                
+                    
+                
+          <hr class="divider" />
+
+           <div id="poweredBy">
+                            <div class="clear"></div>
+                            <div class="clear"></div>
+                            <div class="clear"></div>
+                                                                                        
                                <a href="https://code.google.com/p/hyracks/" title="Hyracks"
class="builtBy">
+        <img class="builtBy"  alt="Hyracks" src="../images/hyrax_ts.png"    />
+      </a>
+                      </div>
+          </div>
+        </div>
+        
+                
+        <div id="bodyColumn"  class="span9" >
+                                  
+            <!-- ! Licensed to the Apache Software Foundation (ASF) under one
+ ! or more contributor license agreements.  See the NOTICE file
+ ! distributed with this work for additional information
+ ! regarding copyright ownership.  The ASF licenses this file
+ ! to you under the Apache License, Version 2.0 (the
+ ! "License"); you may not use this file except in compliance
+ ! with the License.  You may obtain a copy of the License at
+ !
+ !   http://www.apache.org/licenses/LICENSE-2.0
+ !
+ ! Unless required by applicable law or agreed to in writing,
+ ! software distributed under the License is distributed on an
+ ! "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ ! KIND, either express or implied.  See the License for the
+ ! specific language governing permissions and limitations
+ ! under the License.
+ ! --><h1>AsterixDB Support of Similarity Queries</h1>
+<div class="section">
+<h2><a name="Table_of_Contents"></a><a name="toc" id="toc">Table
of Contents</a></h2>
+
+<ul>
+  
+<li><a href="#Motivation">Motivation</a></li>
+  
+<li><a href="#DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a></li>
+  
+<li><a href="#SimilaritySelectionQueries">Similarity Selection Queries</a></li>
+  
+<li><a href="#SimilarityJoinQueries">Similarity Join Queries</a></li>
+  
+<li><a href="#UsingIndexesToSupportSimilarityQueries">Using Indexes to Support
Similarity Queries</a></li>
+</ul></div>
+<div class="section">
+<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>
+<p>Similarity queries are widely used in applications where users need to find records
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>
+<div class="section">
+<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>
+<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>
+<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>
+<div class="section">
+<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>
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
+    where $ed &lt;= 2
+    return $user
+</pre></div></div>
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
+    where $sim &gt;= 0.6f
+    return $user
+</pre></div></div>
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    set simfunction &quot;jaccard&quot;;
+    set simthreshold &quot;0.6f&quot;;
+
+    for $user in dataset('FacebookUsers')
+    where $user.friend-ids ~= [1,5,9,10]
+    return $user
+</pre></div></div>
+<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>
+<div class="section">
+<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>
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    set simfunction &quot;edit-distance&quot;;
+    set simthreshold &quot;3&quot;;
+
+    for $fbu in dataset FacebookUsers
+    return {
+        &quot;id&quot;: $fbu.id,
+        &quot;name&quot;: $fbu.name,
+        &quot;similar-users&quot;: for $t in dataset TweetMessages
+                            let $tu := $t.user
+                            where $tu.name ~= $fbu.name
+                            return {
+                            &quot;twitter-screenname&quot;: $tu.screen-name,
+                            &quot;twitter-name&quot;: $tu.name
+                            }
+    };
+</pre></div></div></div>
+<div class="section">
+<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>
+<p>AsterixDB uses two types of indexes to support similarity queries, namely &#x201c;ngram
index&#x201d; and &#x201c;keyword index&#x201d;.</p>
+<div class="section">
+<h3><a name="NGram_Index"></a>NGram Index</h3>
+<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>
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    create index fbUserIdx on FacebookUsers(name) type ngram(3);
+</pre></div></div>
+<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>
+<div class="section">
+<h4><a name="NGram_Index_usage_case_-_edit-distance"></a>NGram Index usage
case - <a href="functions.html#edit-distance">edit-distance</a></h4>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $ed := edit-distance($user.name, &quot;Suzanna Tilson&quot;)
+    where $ed &lt;= 2
+    return $user
+</pre></div></div></div>
+<div class="section">
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $ed := edit-distance-check($user.name, &quot;Suzanna Tilson&quot;, 2)
+    where $ed[0]
+    return $ed[1]
+</pre></div></div></div>
+<div class="section">
+<h4><a name="NGram_Index_usage_case_-_similarity-jaccard"></a>NGram Index
usage case - <a href="functions.html#similarity-jaccard">similarity-jaccard</a></h4>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $sim := similarity-jaccard($user.friend-ids, [1,5,9,10])
+    where $sim &gt;= 0.6f
+    return $user
+</pre></div></div></div>
+<div class="section">
+<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>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $user in dataset('FacebookUsers')
+    let $sim := similarity-jaccard-check($user.friend-ids, [1,5,9,10], 0.6f)
+    where $sim[0]
+    return $user
+</pre></div></div></div>
+<div class="section">
+<h4><a name="NGram_Index_usage_case_-_contains"></a>NGram Index usage case
- <a href="functions.html#contains">contains()</a></h4>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    for $i in dataset('FacebookMessages')
+    where contains($i.message, &quot;phone&quot;)
+    return {&quot;mid&quot;: $i.message-id, &quot;message&quot;: $i.message}
+</pre></div></div></div></div>
+<div class="section">
+<h3><a name="Keyword_Index"></a>Keyword Index</h3>
+<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 records with this token. The following two examples show how to create keyword index
on two different types:</p>
+<div class="section">
+<h4><a name="Keyword_Index_on_String_Type"></a>Keyword Index on String
Type</h4>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    drop index FacebookMessages.fbMessageIdx if exists;
+    create index fbMessageIdx on FacebookMessages(message) type keyword;
+
+    for $o in dataset('FacebookMessages')
+    let $jacc := similarity-jaccard-check(word-tokens($o.message), word-tokens(&quot;love
like verizon&quot;), 0.2f)
+    where $jacc[0]
+    return $o
+</pre></div></div></div>
+<div class="section">
+<h4><a name="Keyword_Index_on_UnorderedList_Type"></a>Keyword Index on
UnorderedList Type</h4>
+
+<div class="source">
+<div class="source">
+<pre>    use dataverse TinySocial;
+
+    create index fbUserIdx_fids on FacebookUsers(friend-ids) type keyword;
+
+    for $c in dataset('FacebookUsers')
+    let $jacc := similarity-jaccard-check($c.friend-ids, {{3,10}}, 0.5f)
+    where $jacc[0]
+    return $c
+</pre></div></div>
+<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>
+                  </div>
+            </div>
+          </div>
+
+    <hr/>
+
+    <footer>
+            <div class="container-fluid">
+              <div class="row span12">Copyright &copy;                    2015
+                        <a href="http://www.apache.org/">The Apache Software Foundation</a>.
+            All Rights Reserved.      
+                    
+      </div>
+
+                                                                  <?xml version="1.0"
encoding="UTF-8"?>
+<div class="row-fluid">Apache AsterixDB, AsterixDB, Apache, the Apache
+        feather logo, and the Apache AsterixDB project logo are either
+        registered trademarks or trademarks of The Apache Software
+        Foundation in the United States and other countries.
+        All other marks mentioned may be trademarks or registered
+        trademarks of their respective owners.</div>
+                  
+        
+                </div>
+    </footer>
+  </body>
+</html>


Mime
View raw message