{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T22:42:02Z","timestamp":1783204922268,"version":"3.54.6"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>\n            As an essential operation in data cleaning, the similarity join has attracted considerable attention from the database community. In this paper, we study string similarity joins with edit-distance constraints, which find\n            <jats:italic>similar<\/jats:italic>\n            string pairs from two large sets of strings whose edit distance is within a given threshold. Existing algorithms are efficient either for short strings or for long strings, and there is no algorithm that can efficiently and adaptively support both short strings and long strings. To address this problem, we propose a partition-based method called Pass-Join. Pass-Join partitions a string into a set of segments and creates inverted indices for the segments. Then for each string, Pass-Join selects some of its substrings and uses the selected substrings to find candidate pairs using the inverted indices. We devise efficient techniques to select the substrings and prove that our method can minimize the number of selected substrings. We develop novel pruning techniques to efficiently verify the candidate pairs. Experimental results show that our algorithms are efficient for both short strings and long strings, and outperform state-of-the-art methods on real datasets.\n          <\/jats:p>","DOI":"10.14778\/2078331.2078340","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"253-264","source":"Crossref","is-referenced-by-count":122,"title":["Pass-join"],"prefix":"10.14778","volume":"5","author":[{"given":"Guoliang","family":"Li","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiannan","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianhua","family":"Feng","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,11]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","first-page":"945","article-title":"Scalable ad-hoc entity extraction from text collections","volume":"1","author":"Agrawal S.","year":"2008","unstructured":"S. Agrawal , K. Chakrabarti , S. Chaudhuri , and V. Ganti . Scalable ad-hoc entity extraction from text collections . PVLDB , 1 ( 1 ): 945 -- 957 , 2008 . S. Agrawal, K. Chakrabarti, S. Chaudhuri, and V. Ganti. Scalable ad-hoc entity extraction from text collections. PVLDB, 1(1):945--957, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_2_1","first-page":"918","volume-title":"VLDB","author":"Arasu A.","year":"2006","unstructured":"A. Arasu , V. Ganti , and R. Kaushik . Efficient exact set-similarity joins . In VLDB , pages 918 -- 929 , 2006 . A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. In VLDB, pages 918--929, 2006."},{"key":"e_1_2_1_3_1","first-page":"131","volume-title":"WWW","author":"Bayardo R. J.","year":"2007","unstructured":"R. J. Bayardo , Y. Ma , and R. Srikant . Scaling up all pairs similarity search . In WWW , pages 131 -- 140 , 2007 . 10.1145\/1242572.1242591 R. J. Bayardo, Y. Ma, and R. Srikant. Scaling up all pairs similarity search. In WWW, pages 131--140, 2007. 10.1145\/1242572.1242591"},{"key":"e_1_2_1_4_1","first-page":"805","volume-title":"SIGMOD Conference","author":"Chakrabarti K.","year":"2008","unstructured":"K. Chakrabarti , S. Chaudhuri , V. Ganti , and D. Xin . An efficient filter for approximate membership checking . In SIGMOD Conference , pages 805 -- 818 , 2008 . 10.1145\/1376616.1376697 K. Chakrabarti, S. Chaudhuri, V. Ganti, and D. Xin. An efficient filter for approximate membership checking. In SIGMOD Conference, pages 805--818, 2008. 10.1145\/1376616.1376697"},{"key":"e_1_2_1_5_1","first-page":"313","volume-title":"SIGMOD Conference","author":"Chaudhuri S.","year":"2003","unstructured":"S. Chaudhuri , K. Ganjam , V. Ganti , and R. Motwani . Robust and efficient fuzzy match for online data cleaning . In SIGMOD Conference , pages 313 -- 324 , 2003 . 10.1145\/872757.872796 S. Chaudhuri, K. Ganjam, V. Ganti, and R. Motwani. Robust and efficient fuzzy match for online data cleaning. In SIGMOD Conference, pages 313--324, 2003. 10.1145\/872757.872796"},{"key":"e_1_2_1_6_1","first-page":"5","volume-title":"ICDE","author":"Chaudhuri S.","year":"2006","unstructured":"S. Chaudhuri , V. Ganti , and R. Kaushik . A primitive operator for similarity joins in data cleaning . In ICDE , pages 5 -- 16 , 2006 . 10.1109\/ICDE.2006.9 S. Chaudhuri, V. Ganti, and R. Kaushik. A primitive operator for similarity joins in data cleaning. In ICDE, pages 5--16, 2006. 10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_7_1","first-page":"491","volume-title":"VLDB","author":"Gravano L.","year":"2001","unstructured":"L. Gravano , P. G. Ipeirotis , H. V. Jagadish , N. Koudas , S. Muthukrishnan , and D. Srivastava . Approximate string joins in a database (almost) for free . In VLDB , pages 491 -- 500 , 2001 . L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In VLDB, pages 491--500, 2001."},{"key":"e_1_2_1_8_1","first-page":"267","volume-title":"ICDE","author":"Hadjieleftheriou M.","year":"2008","unstructured":"M. Hadjieleftheriou , A. Chandel , N. Koudas , and D. Srivastava . Fast indexes and algorithms for set similarity selection queries . In ICDE , pages 267 -- 276 , 2008 . 10.1109\/ICDE.2008.4497435 M. Hadjieleftheriou, A. Chandel, N. Koudas, and D. Srivastava. Fast indexes and algorithms for set similarity selection queries. In ICDE, pages 267--276, 2008. 10.1109\/ICDE.2008.4497435"},{"key":"e_1_2_1_9_1","first-page":"429","volume-title":"SIGMOD Conference","author":"Hadjieleftheriou M.","year":"2009","unstructured":"M. Hadjieleftheriou , N. Koudas , and D. Srivastava . Incremental maintenance of length normalized indexes for approximate string matching . In SIGMOD Conference , pages 429 -- 440 , 2009 . 10.1145\/1559845.1559891 M. Hadjieleftheriou, N. Koudas, and D. Srivastava. Incremental maintenance of length normalized indexes for approximate string matching. In SIGMOD Conference, pages 429--440, 2009. 10.1145\/1559845.1559891"},{"issue":"1","key":"e_1_2_1_10_1","first-page":"201","article-title":"Hashed samples: selectivity estimators for set similarity selection queries","volume":"1","author":"Hadjieleftheriou M.","year":"2008","unstructured":"M. Hadjieleftheriou , X. Yu , N. Koudas , and D. Srivastava . Hashed samples: selectivity estimators for set similarity selection queries . PVLDB , 1 ( 1 ): 201 -- 212 , 2008 . M. Hadjieleftheriou, X. Yu, N. Koudas, and D. Srivastava. Hashed samples: selectivity estimators for set similarity selection queries. PVLDB, 1(1):201--212, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366104"},{"key":"e_1_2_1_12_1","first-page":"195","volume-title":"VLDB","author":"Lee H.","year":"2007","unstructured":"H. Lee , R. T. Ng , and K. Shim . Extending q-grams to estimate selectivity of string matching with low edit distance . In VLDB , pages 195 -- 206 , 2007 . H. Lee, R. T. Ng, and K. Shim. Extending q-grams to estimate selectivity of string matching with low edit distance. In VLDB, pages 195--206, 2007."},{"issue":"1","key":"e_1_2_1_13_1","first-page":"658","article-title":"Power-law based estimation of set similarity join size","volume":"2","author":"Lee H.","year":"2009","unstructured":"H. Lee , R. T. Ng , and K. Shim . Power-law based estimation of set similarity join size . PVLDB , 2 ( 1 ): 658 -- 669 , 2009 . H. Lee, R. T. Ng, and K. Shim. Power-law based estimation of set similarity join size. PVLDB, 2(1):658--669, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_2_1_15_1","first-page":"529","volume-title":"SIGMOD Conference","author":"Li G.","year":"2011","unstructured":"G. Li , D. Deng , and J. Feng . Faerie: efficient filtering algorithms for approximate dictionary-based entity extraction . In SIGMOD Conference , pages 529 -- 540 , 2011 . 10.1145\/1989323.1989379 G. Li, D. Deng, and J. Feng. Faerie: efficient filtering algorithms for approximate dictionary-based entity extraction. In SIGMOD Conference, pages 529--540, 2011. 10.1145\/1989323.1989379"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_18_1","first-page":"743","volume-title":"SIGMOD Conference","author":"Sarawagi S.","year":"2004","unstructured":"S. Sarawagi and A. Kirpal . Efficient set joins on similarity predicates . In SIGMOD Conference , pages 743 -- 754 , 2004 . 10.1145\/1007568.1007652 S. Sarawagi and A. Kirpal. Efficient set joins on similarity predicates. In SIGMOD Conference, pages 743--754, 2004. 10.1145\/1007568.1007652"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"issue":"1","key":"e_1_2_1_20_1","first-page":"1219","article-title":"Trie-join: Efficient trie-based string similarity joins with edit-distance constraints","volume":"3","author":"Wang J.","year":"2010","unstructured":"J. Wang , G. Li , and J. Feng . Trie-join: Efficient trie-based string similarity joins with edit-distance constraints . PVLDB , 3 ( 1 ): 1219 -- 1230 , 2010 . J. Wang, G. Li, and J. Feng. Trie-join: Efficient trie-based string similarity joins with edit-distance constraints. PVLDB, 3(1):1219--1230, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_21_1","first-page":"458","volume-title":"ICDE","author":"Wang J.","year":"2011","unstructured":"J. Wang , G. Li , and J. Feng . Fast-join: An efficient method for fuzzy token matching based string similarity join . In ICDE , pages 458 -- 469 , 2011 . 10.1109\/ICDE.2011.5767865 J. Wang, G. Li, and J. Feng. Fast-join: An efficient method for fuzzy token matching based string similarity join. In ICDE, pages 458--469, 2011. 10.1109\/ICDE.2011.5767865"},{"key":"e_1_2_1_22_1","volume-title":"SIGMOD Conference","author":"Wang W.","year":"2009","unstructured":"W. Wang , C. Xiao , X. Lin , and C. Zhang . Efficient approximate entity extraction with edit distance constraints . In SIGMOD Conference , 2009 . 10.1145\/1559845.1559925 W. Wang, C. Xiao, X. Lin, and C. Zhang. Efficient approximate entity extraction with edit distance constraints. In SIGMOD Conference, 2009. 10.1145\/1559845.1559925"},{"issue":"1","key":"e_1_2_1_23_1","first-page":"933","article-title":"Ed-join: an efficient algorithm for similarity joins with edit distance constraints","volume":"1","author":"Xiao C.","year":"2008","unstructured":"C. Xiao , W. Wang , and X. Lin . Ed-join: an efficient algorithm for similarity joins with edit distance constraints . PVLDB , 1 ( 1 ): 933 -- 944 , 2008 . C. Xiao, W. Wang, and X. Lin. Ed-join: an efficient algorithm for similarity joins with edit distance constraints. PVLDB, 1(1):933--944, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_24_1","first-page":"916","volume-title":"ICDE","author":"Xiao C.","year":"2009","unstructured":"C. Xiao , W. Wang , X. Lin , and H. Shang . Top-k set similarity joins . In ICDE , pages 916 -- 927 , 2009 . 10.1109\/ICDE.2009.111 C. Xiao, W. Wang, X. Lin, and H. Shang. Top-k set similarity joins. In ICDE, pages 916--927, 2009. 10.1109\/ICDE.2009.111"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367516"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807266"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2078331.2078340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:48Z","timestamp":1672222488000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2078331.2078340"}},"subtitle":["a partition-based method for similarity joins"],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.14778\/2078331.2078340"],"URL":"https:\/\/doi.org\/10.14778\/2078331.2078340","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}