{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:56:07Z","timestamp":1769752567519,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:00:00Z","timestamp":1597881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1525024, IIS-1633215, CCF-1844234"],"award-info":[{"award-number":["CCF-1525024, IIS-1633215, CCF-1844234"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,8,23]]},"DOI":"10.1145\/3394486.3403099","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T23:18:56Z","timestamp":1597965536000},"page":"566-576","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["MinSearch: An Efficient Algorithm for Similarity Search under Edit Distance"],"prefix":"10.1145","author":[{"given":"Haoyu","family":"Zhang","sequence":"first","affiliation":[{"name":"Indiana University Bloomington, Bloomington, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington, Bloomington, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"918","volume-title":"PVLDB","author":"Arasu Arvind","year":"2006","unstructured":"Arvind Arasu , Venkatesh Ganti , and Raghav Kaushik . Efficient exact set-similarity joins . In PVLDB , pages 918 -- 929 , 2006 . Arvind Arasu, Venkatesh Ganti, and Raghav Kaushik. Efficient exact set-similarity joins. In PVLDB, pages 918--929, 2006."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872796"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593675"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544886"},{"key":"e_1_3_2_2_6_1","first-page":"518","volume-title":"PVLDB","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis , Piotr Indyk , and Rajeev Motwani . Similarity search in high dimensions via hashing . In PVLDB , pages 518 -- 529 , 1999 . Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In PVLDB, pages 518--529, 1999."},{"key":"e_1_3_2_2_7_1","first-page":"491","volume-title":"PVLDB","author":"Gravano Luis","year":"2001","unstructured":"Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , and Divesh Srivastava . Approximate string joins in a database (almost) for free . In PVLDB , pages 491 -- 500 , 2001 . Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, and Divesh Srivastava. Approximate string joins in a database (almost) for free. In PVLDB, pages 491--500, 2001."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559891"},{"key":"e_1_3_2_2_9_1","first-page":"1093","volume-title":"KDD","author":"Haoyu Zhang","year":"2019","unstructured":"Zhang Haoyu and Zhang Qin . Minjoin : Efficient edit similarity joins via local hash minima . KDD , pages 1093 -- 1103 , 2019 . Zhang Haoyu and Zhang Qin. Minjoin: Efficient edit similarity joins via local hash minima. KDD, pages 1093--1103, 2019."},{"key":"e_1_3_2_2_10_1","first-page":"85","volume-title":"SIGMOD","author":"Jiannan Wang","year":"2012","unstructured":"Wang Jiannan , Li Guoliang , and Feng Jianhua . Can we beat the prefix filtering?: an adaptive framework for similarity join and search . SIGMOD , pages 85 -- 96 , 2012 . Wang Jiannan, Li Guoliang, and Feng Jianhua. Can we beat the prefix filtering?: an adaptive framework for similarity join and search. SIGMOD, pages 85--96, 2012."},{"key":"e_1_3_2_2_11_1","first-page":"351","volume-title":"PVLDB","author":"Kahveci Tamer","year":"2001","unstructured":"Tamer Kahveci and Ambuj K. Singh . Efficient index structures for string databases . In PVLDB , pages 351 -- 360 , 2001 . Tamer Kahveci and Ambuj K. Singh. Efficient index structures for string databases. In PVLDB, pages 351--360, 2001."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_3_2_2_14_1","first-page":"303","volume-title":"PVLDB","author":"Li Chen","year":"2007","unstructured":"Chen Li , Bin Wang , and Xiaochun Yang . VGRAM : improving performance of approximate queries on string collections using variable-length grams . In PVLDB , pages 303 -- 314 , 2007 . Chen Li, Bin Wang, and Xiaochun Yang. VGRAM: improving performance of approximate queries on string collections using variable-length grams. In PVLDB, pages 303--314, 2007."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989431"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_3_2_2_17_1","volume-title":"Algorithms for approximate string matching. Information and Control, 64(1--3):100--118","author":"Ukkonen Esko","year":"1985","unstructured":"Esko Ukkonen . Algorithms for approximate string matching. Information and Control, 64(1--3):100--118 , 1985 . Esko Ukkonen. Algorithms for approximate string matching. Information and Control, 64(1--3):100--118, 1985."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627706"},{"issue":"1","key":"e_1_3_2_2_19_1","first-page":"1219","article-title":"Efficient trie-based string similarity joins with edit-distance constraints","volume":"3","author":"Wang Jiannan","year":"2010","unstructured":"Jiannan Wang , Guoliang Li , and Jianhua Feng . Trie-join : Efficient trie-based string similarity joins with edit-distance constraints . PVLDB , 3 ( 1 ): 1219 -- 1230 , 2010 . Jiannan Wang, Guoliang Li, and Jianhua 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_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732220"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453957"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367516"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v24i1.7527"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0449-y"},{"key":"e_1_3_2_2_25_1","first-page":"997","volume-title":"SIGMOD","author":"Zhai Jiaqi","year":"2011","unstructured":"Jiaqi Zhai , Yin Lou , and Johannes Gehrke . ATLAS : a probabilistic algorithm for high dimensional similarity search . In SIGMOD , pages 997 -- 1008 , 2011 . Jiaqi Zhai, Yin Lou, and Johannes Gehrke. ATLAS: a probabilistic algorithm for high dimensional similarity search. In SIGMOD, pages 997--1008, 2011."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807266"}],"event":{"name":"KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event CA USA","acronym":"KDD '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403099","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403099","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:38Z","timestamp":1750200098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,20]]},"references-count":27,"alternative-id":["10.1145\/3394486.3403099","10.1145\/3394486"],"URL":"https:\/\/doi.org\/10.1145\/3394486.3403099","relation":{},"subject":[],"published":{"date-parts":[[2020,8,20]]},"assertion":[{"value":"2020-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}