FrepJoin: an efficient partition-based algorithm for edit similarity join

Ji-zhou LUO; Sheng-fei SHI; Hong-zhi WANG; Jian-zhong LI

doi:10.1631/FITEE.1601347

Your Location：

Home >

Browse articles >

FrepJoin: an efficient partition-based algorithm for edit similarity join

Regular Papers | Updated：2022-05-19

- FrepJoin: an efficient partition-based algorithm for edit similarity join
- 频率连接：基于数据划分的一种高效字符串相似性连接算法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 10, Pages: 1499-1510(2017)
- Affiliations：
  
  School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
  Guangdong Key Laboratory of Popular High Performance Computers, Key Laboratory of Service Computing and Application, Shenzhen 518000, China
- Author bio：
  
  Ji-zhou LUO, luojizhou@hit.edu.cn
  [ "SHI Sheng-fei, E-mail: shengfei@hit.edu.cn" ]
  [ "WANG Hong-zhi, E-mail: wangzh@hit.edu.cn" ]
  [ "LI Jian-zhong, E-mail: lijzh@hit.edu.cn" ]
- Funds：
- DOI：10.1631/FITEE.1601347
  CLC： TP311.13
- Received：17 June 2016，
  
  Revised：2017-11-;6，
  
  Published：2017-10
- Accepted：
Scan QR Code
Ji-zhou LUO, Sheng-fei SHI, Hong-zhi WANG, et al. FrepJoin: an efficient partition-based algorithm for edit similarity join[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1499-1510.
DOI：

Ji-zhou LUO, Sheng-fei SHI, Hong-zhi WANG, et al. FrepJoin: an efficient partition-based algorithm for edit similarity join[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1499-1510. DOI： 10.1631/FITEE.1601347.

摘要

字符串相似性连接（string similarity join

SSJ）在很多应用中，特别是在需要找出重复对象的应用中发挥着关键作用。本文关注基于编辑距离的字符串相似性连接。现有算法大多采用先过滤再细化的框架，使得它们很难发现和利用字符串子集间的不相似性，也很难利用如字符频率这样的统计信息。本研究提出了一种基于数据划分的字符串相似性连接算法，它充分利用了这种统计信息。采用频率向量将字符串集划分成一系列较小的子集，使得子集之间的不相似性很容易被发现。本文提出的新算法利用划分后的数据高效地对字符串进行相似性。此外，本文还给出了一个新的过滤器，它能利用字符频率来过滤很多能够通过现有过滤器的不相似字符串。真实数据集上的试验表明，本文提出的算法性能较现有算法有较大幅度的提升。

Abstract

String similarity join (SSJ) is essential for many applications where near-duplicate objects need to be found. This paper targets SSJ with edit distance constraints. The existing algorithms usually adopt the filter-andrefine framework. They cannot catch the dissimilarity between string subsets

and do not fully exploit the statistics such as the frequencies of characters. We investigate to develop a partition-based algorithm by using such statistics. The frequency vectors are used to partition datasets into data chunks with dissimilarity between them being caught easily. A novel algorithm is designed to accelerate SSJ via the partitioned data. A new filter is proposed to leverage the statistics to avoid computing edit distances for a noticeable proportion of candidate pairs which survive the existing filters. Our algorithm outperforms alternative methods notably on real datasets.

关键词

Keywords

references

F.N. Afrati , , , A.D. Sarma , , , D. Menestrina , , , 等 . . Fuzzy joins using MapReduce . . Int. Conf. on Data Engineering , , 2012 . . p.498 - - 509 . . DOI: 10.1109/ICDE.2012.66 http://doi.org/10.1109/ICDE.2012.66 . .

A. Arasu , , , V. Ganti , , , R. Kaushik . . Efficient exact set-similarity joins . . Int. Conf. on Very Large Data Bases , , 2006 . . p.918 - - 929 . . . .

R.J. Bayardo , , , Y. Ma , , , R. Srikant . . Scaling up all pairs similarity search . . Int. World Wide Web Conf. , , 2007 . . p.131 - - 140 . . DOI: 10.1145/1242572.1242591 http://doi.org/10.1145/1242572.1242591 . .

S. Chaudhuri , , , K. Ganjam , , , V. Ganti , , , 等 . . Robust and efficient fuzzy match for online data cleaning . . Int. SIGMOD Conf. on Management of Data , , 2003 . . p.313 - - 324 . . DOI: 10.1145/872757.872796 http://doi.org/10.1145/872757.872796 . .

S. Chaudhuri , , , V. Ganti , , , R. Kaushik . . Data debugger: an operator-centric approach for data quality solutions . . IEEE Data Eng. Bull. , , 2006a . . 29 ( ( 2 ): ): 60 - - 66 . . . .

S. Chaudhuri , , , V. Ganti , , , R. Kaushik . . A primitive operator for similarity joins in data cleaning . . Int. Conf. on Data Engineering , , 2006b . . p.687 - - 698 . . DOI: 10.1109/ICDE.2006.9 http://doi.org/10.1109/ICDE.2006.9 . .

X. Dong , , , A.Y. Halevy , , , C. Yu . . Data integration with uncertainty . . Int. Conf. on Very Large Data Bases , , 2007 . . p.687 - - 698 . . . .

J. Feng , , , J. Wang , , , G. Li . . Trie-join: a trie-based method for efficient string similarity joins . . VLDB J. , , 2012 . . 21 ( ( 4 ): ): 437 - - 461 . . DOI: 10.1007/s00778-011-0252-8 http://doi.org/10.1007/s00778-011-0252-8 . .

T. Ge , , , Z. Li . . Approximate substring matching over uncertain strings . . Proc. VLDB Endow. , , 2011 . . 4 ( ( 11 ): ): 772 - - 782 . . . .

L. Gravano , , , P.G. Ipeirotis , , , H.V. Jagadish , , , 等 . . Approximate string joins in a database (almost) for free . . Int. Conf. on Very Large Data Bases , , 2001 . . p.491 - - 500 . . . .

M. Hadjieleftheriou , , , D. Srivastava . . Weighted SetBased String Similarity . . Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. AT&T Lab-Research. , , 2010 . . .

M.R. Henzinger . . Finding near-duplicate web pages: a large-scale evaluation of algorithms . . Int. ACM SIGIR Conf. on Research and Development in Information Retrieval , , 2006 . . p.284 - - 291 . . DOI: 10.1145/1148170.1148222 http://doi.org/10.1145/1148170.1148222 . .

S. Ji , , , G. Li , , , C. Li , , , 等 . . Efficient interactive fuzzy keyword search . . Int. World Wide Web Conf. , , 2009 . . p.371 - - 380 . . DOI: 10.1145/1526709.1526760 http://doi.org/10.1145/1526709.1526760 . .

C. Li , , , J. Lu , , , Y. Lu . . Efficient merging and filtering algorithms for approximate string searches . . Int. Conf. on Data Engineering , , 2008 . . p.257 - - 266 . . DOI: 10.1109/ICDE.2008.4497434 http://doi.org/10.1109/ICDE.2008.4497434 . .

G. Li , , , D. Deng , , , J. Wang , , , 等 . . Pass-Join: a partition-based method for similarity joins . . Proc. VLDB Endow. , , 2011 . . 5 ( ( 3 ): ): 253 - - 264 . . DOI: 10.14778/2078331.2078340 http://doi.org/10.14778/2078331.2078340 . .

A. Metwally , , , D. Agrawal , , , A.E. Abbadi . . Detectives: detecting coalition hit inflation attacks in advertising networks streams . . Int. World Wide Web Conf. , , 2007 . . p.241 - - 250 . . DOI: 10.1145/1242572.1242606 http://doi.org/10.1145/1242572.1242606 . .

G. Navarro , , , L. Salmela . . Indexing variable length substrings for exact and approximate matching . . Int. Symp. on String Processing and Information Retrieval , , 2009 . . p.214 - - 221 . . DOI: 10.1007/978-3-642-03784-9_21 http://doi.org/10.1007/978-3-642-03784-9_21 . .

J. Qin , , , W. Wang , , , C. Xiao , , , 等 . . Vchunkjoin: an efficient algorithm for edit similarity joins . . Trans. Knowl. Dat. Eng. , , 2013 . . 25 ( ( 8 ): ): 1916 - - 1929 . . DOI: 10.1109/TKDE.2012.79 http://doi.org/10.1109/TKDE.2012.79 . .

S. Sarawagi , , , A. Kirpal . . Efficient set joins on similarity predicates . . Int. SIGMOD Conf. on Management of Data , , 2004 . . p.743 - - 754 . . DOI: 10.1145/1007568.1007652 http://doi.org/10.1145/1007568.1007652 . .

D.W. Scott . . On optimal and data-based histograms . . Biometrika , , 1979 . . 66 605 - - 610 . . DOI: 10.1093/biomet/66.3.605 http://doi.org/10.1093/biomet/66.3.605 . .

R. Vernica , , , M.J. Carey , , , C. Li . . Efficient parallel set-similarity joins using MapReduce . . Int. SIGMOD Conf. on Management of Data , , 2010 . . p.495 - - 506 . . DOI: 10.1145/1807167.1807222 http://doi.org/10.1145/1807167.1807222 . .

J. Wang , , , G. Li , , , J. Feng . . Fast-join: an efficient method for fuzzy token matching based string similarity join . . Int. Conf. on Data Engineering , , 2011 . . p.458 - - 469 . . DOI: 10.1109/ICDE.2011.5767865 http://doi.org/10.1109/ICDE.2011.5767865 . .

W. Wang , , , C. Xiao , , , X. Lin , , , 等 . . Efficient approximate entity extraction with edit distance constraints . . Int. SIGMOD Conf. on Management of Data , , 2009 . . p.759 - - 770 . . DOI: 10.1145/1559845.1559925 http://doi.org/10.1145/1559845.1559925 . .

C. Xiao , , , W. Wang , , , X. Lin . . Ed-Join: an efficient algorithm for similarity joins with edit distance constraints . . Proc. VLDB Endow. , , 2008a . . 1 ( ( 1 ): ): 933 - - 944 . . DOI: 10.14778/1453856.1453957 http://doi.org/10.14778/1453856.1453957 . .

C. Xiao , , , W. Wang , , , X. Lin , , , 等 . . Efficient similarity joins for near duplicate detection . . Int. World Wide Web Conf. , , 2008b . . p.131 - - 140 . . DOI: 10.1145/2000824.2000825 http://doi.org/10.1145/2000824.2000825 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰