清华大学：Pass-Join（A Partition based Method for Similarity Joins）

Pass-Join:A Partition based Method for Similarity Joins Guoliang Li (Tsinghua,China) Dong Deng (Tsinghua,China) Jiannan Wang (Tsinghua,China) h心 -1911- Jianhua Feng (Tsinghua,China)

Guoliang Li (Tsinghua, China) Dong Deng (Tsinghua, China) Jiannan Wang (Tsinghua, China) Jianhua Feng (Tsinghua, China)

Real-world Data is Rather Dirty! a DBLP Complete search ● Typo in“aut 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. □Awvw:051011 Argyris Zymnis Typo in“ title relaxe Yair Bartal, 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 1/29/2021 related PassJoin a VLDB2012

 Typo in “author”  Typo in “title” relaxed related Argyrios Zymnis Argyris Zymnis DBLP Complete Search 1/29/2021 Real-world Data is Rather Dirty！ PassJoin @ VLDB2012 2

Similarity Join Equal Join Datasets Dataset s Conference Conference VLDB CIDR SIGMOD SIGMOD ICDE PVLDB 20/2021 PassJoin a VLDB2012

Similarity Join 1/29/2021 PassJoin @ VLDB2012 3 Conference VLDB SIGMOD ICDE Conference CIDR SIGMOD PVLDB Dataset R Dataset S Equal Join

Similarity Join Similarity join Datasets Dataset s Conference Conference VLDB CIDR SIGMOD SIGMOD ICDE PVLDB 20/2021 PassJoin a VLDB2012

Similarity Join 1/29/2021 PassJoin @ VLDB2012 4 Conference VLDB SIGMOD ICDE Conference CIDR SIGMOD PVLDB Dataset R Dataset S Similarity Join

Applications o Data Cleaning and Integration Near duplicate object detection o Collaborative Filtering 20/2021 PassJoin a VLDB2012

Applications Data Cleaning and Integration Near Duplicate Object Detection Collaborative Filtering  …….. 1/29/2021 PassJoin @ VLDB2012 5

Edit distance ED(r s): The minimum number of single-character edit operations(insertion/deletion/substitution to transform r to s Forexample: ED(hilton, huston)=2 hilton substitute i with u hulton substitute l with u huston Property:ED(r, s)2IIrI-Isl 20/2021 PassJoin a VLDB2012

 ED(r, s): The minimum number of single-character edit operations(insertion/deletion/substitution) to transform r to s.  For example: ED(hilton, huston) = 2  Property: ED(r, s) ≥ ||r|-|s|| Edit Distance 1/29/2021 PassJoin @ VLDB2012 6 hilton hulton huston substitute i with u substitute l with u

Problem formulation Give threshold t=3 [ID Strings $1 vankatesh S2 avataresha s3 kaushic chaduri S4 kaushik chakra S5 kaushuk chadhui s6=5ED=13ED=12 ED=14ED=12ED=12ED=12 ED=14ED=4ED=8 ED=4ED=8 1/29/2021 PassJoin a VLDB2012

Problem Formulation 1/29/2021 PassJoin @ VLDB2012 7 Give threshold τ=3 ED =5 ED =13 ED =12 ED =12 ED =14 ED =12 ED =12 ED =12 ED =14 ED =5 ED =4 ED =8 ED =4 ED =3 ED =8

Filter-and-refine methods Basic idea e Filter a large number of dissimilar string pairs Verify the remaining potentially similar pairs 20/2021 PassJoin a VLDB2012

Filter-and-refine Methods Basic idea  Filter a large number of dissimilar string pairs  Verify the remaining potentially similar pairs 1/29/2021 PassJoin @ VLDB2012 8

Filter-and-refine methods Give threshold t=3 DI Strings Length s1 vankatesh 9 Pruning Condition. s2/ avataresha s3 kaushic chaduri 15 S 3 s4 kaushik chakrab15 ss kaushuk chadhui|15 s6 caushik chakrabar|17 ED≤s1,2>=5113B1412E“112 E1当-44E23212E=5ED=4ED=8 ED=4ED=3ED=8 1/29/2021 PassJoin a VLDB2012

Filter-and-refine Methods 1/29/2021 PassJoin @ VLDB2012 9 Give threshold τ=3 ED =5 ED =13 ED =12 ED =12 ED =14 ED =12 ED =12 ED =12 ED =14 ED =5 ED =4 ED =8 ED =4 ED =3 ED =8 Pruning Condition: ||si | - |sj || > 3

Filter-and-refine methods ● Basic idea Filter a large number of dissimilar string pairs Verify the remaining potentially similar pairs Drawbacks o Need to tune parameters Bad for short strings 20/2021 PassJoin a VLDB2012

Filter-and-refine Methods Basic idea  Filter a large number of dissimilar string pairs  Verify the remaining potentially similar pairs Drawbacks  Need to tune parameters  Bad for short strings 1/29/2021 PassJoin @ VLDB2012 10