{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:41:02Z","timestamp":1776357662472,"version":"3.51.2"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            Set similarity join is an important problem with many applications in data discovery, cleaning and integration. To increase robustness, fuzzy set similarity join calculates the similarity of two sets based on maximum weighted bipartite matching instead of set overlap. This allows pairs of elements, represented as sets or strings, to also match approximately rather than exactly, e.g., based on Jaccard similarity or edit distance. However, this significantly increases the verification cost, making even more important the need for efficient and effective filtering techniques to reduce the number of candidate pairs. The current state-of-the-art algorithm relies on similarity computations between pairs of elements to filter candidates. In this paper, we propose token-based instead of element-based filtering, showing that it is significantly more lightweight, while offering similar or even better pruning effectiveness. Moreover, we address the top-\n            <jats:italic>k<\/jats:italic>\n            variant of the problem, alleviating the need for a user-specified similarity threshold. We also propose early termination to reduce the cost of verification. Our experimental results on six real-world datasets show that our approach always outperforms the state of the art, being an order of magnitude faster on average.\n          <\/jats:p>","DOI":"10.14778\/3574245.3574263","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"790-802","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["TokenJoin"],"prefix":"10.14778","volume":"16","author":[{"given":"Alexandros","family":"Zeakis","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens &amp; \"Athena\" RC, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Skoutas","sequence":"additional","affiliation":[{"name":"\"Athena\" RC, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitris","family":"Sacharidis","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Odysseas","family":"Papapetrou","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manolis","family":"Koubarakis","sequence":"additional","affiliation":[{"name":"National and Kapodistrian University of Athens, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Arvind Arasu Venkatesh Ganti and Raghav Kaushik. 2006. Efficient Exact Set-Similarity Joins. In VLDB. 918--929.  Arvind Arasu Venkatesh Ganti and Raghav Kaushik. 2006. Efficient Exact Set-Similarity Joins. In VLDB. 918--929."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Roberto J Bayardo Yiming Ma and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In WWW. 131--140.  Roberto J Bayardo Yiming Ma and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In WWW. 131--140.","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2428536.2428537"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Surajit Chaudhuri Venkatesh Ganti and Raghav Kaushik. 2006. A Primitive Operator for Similarity Joins in Data Cleaning. In ICDE. 5.  Surajit Chaudhuri Venkatesh Ganti and Raghav Kaushik. 2006. A Primitive Operator for Similarity Joins in Data Cleaning. In ICDE. 5.","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Tobias Christiani Rasmus Pagh and Johan Sivertsen. 2018. Scalable and Robust Set Similarity Join. In ICDE. 1240--1243.  Tobias Christiani Rasmus Pagh and Johan Sivertsen. 2018. Scalable and Robust Set Similarity Join. In ICDE. 1240--1243.","DOI":"10.1109\/ICDE.2018.00120"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115413"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231760"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6502"},{"key":"e_1_2_1_9_1","unstructured":"Luis Gravano Panagiotis G. Ipeirotis H. V. Jagadish Nick Koudas S. Muthukrishnan and Divesh Srivastava. 2001. Approximate String Joins in a Database (Almost) for Free. In VLDB. 491--500.  Luis Gravano Panagiotis G. Ipeirotis H. V. Jagadish Nick Koudas S. Muthukrishnan and Divesh Srivastava. 2001. Approximate String Joins in a Database (Almost) for Free. In VLDB. 491--500."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732299"},{"key":"e_1_2_1_11_1","volume-title":"The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1-2","author":"Kuhn Harold W","year":"1955","unstructured":"Harold W Kuhn . 1955. The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1-2 ( 1955 ), 83--97. Harold W Kuhn. 1955. The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1-2 (1955), 83--97."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2309131"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2947618.2947620"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_15_1","volume-title":"Blocking and Filtering Techniques for Entity Resolution: A Survey. ACM Comput. Surv. 53, 2","author":"Papadakis George","year":"2020","unstructured":"George Papadakis , Dimitrios Skoutas , Emmanouil Thanos , and Themis Palpanas . 2020. Blocking and Filtering Techniques for Entity Resolution: A Survey. ACM Comput. Surv. 53, 2 ( 2020 ), 31:1--31:42. George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas. 2020. Blocking and Filtering Techniques for Entity Resolution: A Survey. ACM Comput. Surv. 53, 2 (2020), 31:1--31:42."},{"key":"e_1_2_1_16_1","unstructured":"Jianbin Qin Wei Wang Yifei Lu Chuan Xiao and Xuemin Lin. 2011. Efficient exact edit similarity query processing with the asymmetric signature scheme. In SIGMOD. 1033--1044.  Jianbin Qin Wei Wang Yifei Lu Chuan Xiao and Xuemin Lin. 2011. Efficient exact edit similarity query processing with the asymmetric signature scheme. In SIGMOD. 1033--1044."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.07.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Sunita Sarawagi and Alok Kirpal. 2004. Efficient set joins on similarity predicates. In SIGMOD. 743--754.  Sunita Sarawagi and Alok Kirpal. 2004. Efficient set joins on similarity predicates. In SIGMOD. 743--754.","DOI":"10.1145\/1007568.1007652"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627706"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Jiannan Wang Guoliang Li and Jianhua Feng. 2012. Can we beat the prefix filtering? An adaptive framework for similarity join and search. In SIGMOD. 85--96.  Jiannan Wang Guoliang Li and Jianhua Feng. 2012. Can we beat the prefix filtering? An adaptive framework for similarity join and search. In SIGMOD. 85--96.","DOI":"10.1145\/2213836.2213847"},{"key":"e_1_2_1_22_1","volume-title":"Extending string similarity join to tolerant fuzzy token matching. TODS 39, 1","author":"Wang Jiannan","year":"2014","unstructured":"Jiannan Wang , Guoliang Li , and Jianhua Feng . 2014. Extending string similarity join to tolerant fuzzy token matching. TODS 39, 1 ( 2014 ), 7:1--7:45. Jiannan Wang, Guoliang Li, and Jianhua Feng. 2014. Extending string similarity join to tolerant fuzzy token matching. TODS 39, 1 (2014), 7:1--7:45."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Jin Wang Chunbin Lin and Carlo Zaniolo. 2019. MF-Join: Efficient Fuzzy String Similarity Join with Multi-level Filtering. In ICDE. 386--397.  Jin Wang Chunbin Lin and Carlo Zaniolo. 2019. MF-Join: Efficient Fuzzy String Similarity Join with Multi-level Filtering. In ICDE. 386--397.","DOI":"10.1109\/ICDE.2019.00042"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.79"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099624"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453957"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Chuan Xiao Wei Wang Xuemin Lin and Haichuan Shang. 2009. Top-k Set Similarity Joins. In ICDE. 916--927.  Chuan Xiao Wei Wang Xuemin Lin and Haichuan Shang. 2009. Top-k Set Similarity Joins. In ICDE. 916--927.","DOI":"10.1109\/ICDE.2009.111"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-015-5900-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1078"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Jiaqi Zhai Yin Lou and Johannes Gehrke. 2011. ATLAS: a probabilistic algorithm for high dimensional similarity search. In SIGMOD. 997--1008.  Jiaqi Zhai Yin Lou and Johannes Gehrke. 2011. ATLAS: a probabilistic algorithm for high dimensional similarity search. In SIGMOD. 997--1008.","DOI":"10.1145\/1989323.1989428"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Yong Zhang Xiuxing Li Jin Wang Ying Zhang Chunxiao Xing and Xiaojie Yuan. 2017. An Efficient Framework for Exact Set Similarity Search Using Tree Structure Indexes. In ICDE. 759--770.  Yong Zhang Xiuxing Li Jin Wang Ying Zhang Chunxiao Xing and Xiaojie Yuan. 2017. An Efficient Framework for Exact Set Similarity Search Using Tree Structure Indexes. In ICDE. 759--770.","DOI":"10.1109\/ICDE.2017.127"},{"key":"e_1_2_1_33_1","volume-title":"Beng Chin Ooi, and Divesh Srivastava","author":"Zhang Zhenjie","year":"2010","unstructured":"Zhenjie Zhang , Marios Hadjieleftheriou , Beng Chin Ooi, and Divesh Srivastava . 2010 . Bed-tree: an all-purpose index structure for string similarity search based on edit distance. In SIGMOD. 915--926. Zhenjie Zhang, Marios Hadjieleftheriou, Beng Chin Ooi, and Divesh Srivastava. 2010. Bed-tree: an all-purpose index structure for string similarity search based on edit distance. In SIGMOD. 915--926."},{"key":"e_1_2_1_34_1","volume-title":"Miller","author":"Zhu Erkang","year":"2019","unstructured":"Erkang Zhu , Dong Deng , Fatemeh Nargesian , and Ren\u00e9e J . Miller . 2019 . JOSIE : Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD. 847--864. Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Ren\u00e9e J. Miller. 2019. JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD. 847--864."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:15:11Z","timestamp":1677021311000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574263"}},"subtitle":["Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching"],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574263"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574263","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}