清华大学：A Pivotal Prefix Based Filtering Algorithm for String Similarity Search（PPT讲稿）

snowbird UT. USA. 2014 A Pivotal Prefix Based Filtering Algorithm for String Similarity search Dong deng, guoliang Li, Jianhua Feng Database Group, Tsinghua University 小 1911 Present by dong deng

Dong Deng, Guoliang Li, Jianhua Feng Database Group, Tsinghua University Present by Dong Deng A Pivotal Prefix Based Filtering Algorithm for String Similarity Search

Search is Important Google Searches per Year 1,600,000,000,000 ■ Search queries 1,200,000,000,000 800000,000,000 40,000,000,000 19992000200120022003200420052006200720082009201020112012 Google searches per Year Source:http://www.internetlivestats.com/google-search-statistics/

Search is Important Source: http://www.internetlivestats.com/google-search-statistics/ Google Searches per Year

Speed matters But when questions aren' t answered quickly, people ask less GOOGLE FOUND THAT SLOWING SEARCH RESULTS BY JUST 4/10THS OF A SECOND would reduce the number of searches by 8,000,000 a d Source

Speed Matters Source:

Data is dirty DBLP Complete Search ypos Argyrios zymnis 008 2EE Argyrios Zymis, Stephen P. Boyd, Dimitry Ml. Gorinevsky: Mixed state estimation for a linear Gaussi an Markov model. CDC2008:3219-3226 I EE Argyris Zymmis, Stephen P. Boyd, Dimitry M. Gorinevsky: Mixed state estimation for a linear Gaussian Markov model. cAo00:1011 argyris Zymnis relaxed E Yai I, Moses Charikar, Piotr Indyk: On page migration and otherrelaxed task systems. Theor. Comput. Sci. Tcs)268(1):43-6(2001) 1997 1 EE Yair Bartal, Moses Charikar, Piotr Indyk: On Page Migration and Other Related Task Systems. SODA 1997: 43-52 related

Data is Dirty • Typos • Typo in “title” relaxed related Argyrios Zymnis Argyris Zymnis DBLP Complete Search

Similarity Search Query All the strings similar to the query String Dataset

Similarity Search Query String Dataset All the strings similar to the query

Edit distance ED( s): The min number of edit operations (insertion/deletion/substitution) needed to transform r to s For example: ED(sigcom, sigmod )=2 sitcom substitute c with m sIemon substitute m with d sigmod

• ED(r, s): The min number of edit operations (insertion/deletion/substitution) needed to transform r to s. • For example: ED(sigcom, sigmod) = 2 Edit Distance sigcom sigmom sigmod substitute c with m substitute m with d

Problem definition DEFINITION 1 (STRING SIMILARITY SEARCH). Given a string dataset R, a query string s, and an edit-distance thresh old T, the string similarity search with edit-distance con- straints finds all strings r ER such that ed(r,S)<T id string Query string lmyouteca s= yotubecom"andτ=2 r2 ubuntucom r3 utubbecou r4 youtbecom r5 yoytubeca ed(s, r4<=2 output ra as a result string dataset R

Problem Definition Query string s = “yotubecom” and τ = 2 string dataset R ed(s, r4 ) <= 2 output r4 as a result

Application Spell checking Copy detection Entity Linking ·Bⅰ informatic

Application • Spell Checking • Copy Detection • Entity Linking • Bioinformatic …

Challenge Naive method Time complexity: for each query O(RIs t

Challenge Naïve Method Time complexity: for each query 𝑂 |𝑅| |𝑠| τ

Filter-and-Verification framework Query string s Filter: Index No es Dataset r Signature()∩ Verify: Results Signature (r)=o? ED(rs)≤τ? Threshold T Pruning power Filtering Cost depends on depends on Sig(r)Ix(sig(s)) and Index: (sig(r)I(Probe set size) min((sig(r)(Sig(s) No Index: (sig(r)+(sig(s)I

No Filter-and-Verification Framework Dataset R Threshold τ Query string s Results Filter: Signature(s) ∩ Signature(r) = ϕ? Verify: ED(r,s) ≤ τ? Yes Index