Blame - aql/similarity.html - incubator-asterixdb-site

<h2><a name="Motivation" id="Motivation">Motivation</a> <font size="4"><a href="#toc">[Back to TOC]</a></font><a name="Motivation_Back_to_TOC"></a></h2>

217

<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’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>

218

219

<h2><a name="DataTypesAndSimilarityFunctions" id="DataTypesAndSimilarityFunctions">Data Types and Similarity Functions</a> <font size="4"><a href="#toc">[Back to TOC]</a></font><a name="Data_Types_and_Similarity_Functions_Back_to_TOC"></a></h2>

220

<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 “n” (called “n-grams”) and define the Jaccard similarity between the two gram sets of the two strings. Formally, the “n-grams” of a string are its substrings of length “n”. For instance, the 3-grams of the string <tt>schwarzenegger</tt> are <tt>sch</tt>, <tt>chw</tt>, <tt>hwa</tt>, …, <tt>ger</tt>.</p>

221

<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>

222

223

<h2><a name="SimilaritySelectionQueries" id="SimilaritySelectionQueries">Similarity Selection Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font><a name="Similarity_Selection_Queries_Back_to_TOC"></a></h2>

224

<p>The following <a href="functions.html#edit-distance">query</a> 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>

225

226

227

<pre> use dataverse TinySocial;

228

229

for $user in dataset('FacebookUsers')

230

let $ed := edit-distance($user.name, "Suzanna Tilson")

where $ed <= 2

return $user

</pre></div>

<p>The following <a href="functions.html#similarity-jaccard">query</a> asks for all the Facebook users whose set of friend ids is similar to <tt>[1,5,9]</tt>, i.e., their Jaccard similarity is at least 0.6.</p>

235

236

237

<pre> use dataverse TinySocial;

238

239

for $user in dataset('FacebookUsers')

240

let $sim := similarity-jaccard($user.friend-ids, [1,5,9])

where $sim >= 0.6f

return $user

</pre></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 “set” statements earlier. For instance, the above query can be equivalently written as:</p>

245

246

247

<pre> use dataverse TinySocial;

248

249

set simfunction "jaccard";

250

set simthreshold "0.6f";

251

252

for $user in dataset('FacebookUsers')

253

where $user.friend-ids ~= [1,5,9]

254

return $user

255

</pre></div>

256

<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>

257

258

<h2><a name="SimilarityJoinQueries" id="SimilarityJoinQueries">Similarity Join Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font><a name="Similarity_Join_Queries_Back_to_TOC"></a></h2>

259

<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>

260

261

262

<pre> use dataverse TinySocial;

263

264

set simfunction "edit-distance";

265

set simthreshold "3";

266

267

for $fbu in dataset FacebookUsers

return {

"id": $fbu.id,

"name": $fbu.name,

"similar-users": for $t in dataset TweetMessages

272

let $tu := $t.user

273

where $tu.name ~= $fbu.name

274

return {

275

"twitter-screenname": $tu.screen-name,

276

"twitter-name": $tu.name

}

};

</pre></div></div>

<h2><a name="UsingIndexesToSupportSimilarityQueries" id="UsingIndexesToSupportSimilarityQueries">Using Indexes to Support Similarity Queries</a> <font size="4"><a href="#toc">[Back to TOC]</a></font><a name="Using_Indexes_to_Support_Similarity_Queries_Back_to_TOC"></a></h2>

282

<p>AsterixDB uses two types of indexes to support similarity queries, namely “ngram index” and “keyword index”.</p>

283

284

<h3>NGram Index<a name="NGram_Index"></a></h3>

285

<p>An “ngram index” 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>

286

<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>

287

288

289

<pre> use dataverse TinySocial;

290

291

create index fbUserIdx on FacebookUsers(name) type ngram(3);

292

</pre></div>

293

<p>The number “3” in “ngram(3)” is the length “n” 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 “<a href="functions.html#contains">contains()</a>” 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>

294

295

<h4>NGram Index usage case - <a href="functions.html#edit-distance">edit-distance</a><a name="NGram_Index_usage_case_-_edit-distance"></a></h4>

296

297

298

<pre> use dataverse TinySocial;

299

300

for $user in dataset('FacebookUsers')

301

let $ed := edit-distance($user.name, "Suzanna Tilson")

where $ed <= 2

return $user

</pre></div></div>

<h4>NGram Index usage case - <a href="functions.html#edit-distance-check">edit-distance-check</a><a name="NGram_Index_usage_case_-_edit-distance-check"></a></h4>

307

308

309

<pre> use dataverse TinySocial;

310

311

for $user in dataset('FacebookUsers')

312

let $ed := edit-distance-check($user.name, "Suzanna Tilson", 2)

where $ed[0]

return $ed[1]

</pre></div></div>

<h4>NGram Index usage case - <a href="functions.html#similarity-jaccard">similarity-jaccard</a><a name="NGram_Index_usage_case_-_similarity-jaccard"></a></h4>

318

319

320

<pre> use dataverse TinySocial;

321

322

for $user in dataset('FacebookUsers')

323

let $sim := similarity-jaccard($user.friend-ids, [1,5,9])

where $sim >= 0.6f

return $user

</pre></div></div>

<h4>NGram Index usage case - <a href="functions.html#similarity-jaccard-check">similarity-jaccard-check</a><a name="NGram_Index_usage_case_-_similarity-jaccard-check"></a></h4>

329

330

331

<pre> use dataverse TinySocial;

332

333

for $user in dataset('FacebookUsers')

334

let $sim := similarity-jaccard($user.friend-ids, [1,5,9])

where $sim >= 0.6f

return $user

</pre></div></div>

<h4>NGram Index usage case - <a href="functions.html#contains">contains()</a><a name="NGram_Index_usage_case_-_contains"></a></h4>

340

341

342

<pre> use dataverse TinySocial;

343

344

for $i in dataset('FacebookMessages')

345

where contains($i.message, "phone")

346

return {"mid": $i.message-id, "message": $i.message}

347

</pre></div></div></div>

348

349

<h3>Keyword Index<a name="Keyword_Index"></a></h3>

350

<p>A “keyword index” 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>

351

352

<h4>Keyword Index on String Type<a name="Keyword_Index_on_String_Type"></a></h4>

353

354

355

<pre> use dataverse TinySocial;

356

357

create index fbMessageIdx on FacebookMessages(message) type keyword;

358

359

for $o in dataset('FacebookMessages')

360

let $jacc := similarity-jaccard-check(word-tokens($o.message), word-tokens("love like verizon"), 0.2f)

where $jacc[0]

return $o

</pre></div></div>

<h4>Keyword Index on UnorderedList Type<a name="Keyword_Index_on_UnorderedList_Type"></a></h4>

366

367

368

<pre> use dataverse TinySocial;

369

370

create index fbUserIdx_fids on FacebookUsers(friend-ids) type keyword;

371

372

for $c in dataset('FacebookUsers')

373

let $jacc := similarity-jaccard-check($c.friend-ids, {{3,10}}, 0.5f)

where $jacc[0]

return $c

</pre></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/>