{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T04:44:39Z","timestamp":1761108279625},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,12,17]],"date-time":"2016-12-17T00:00:00Z","timestamp":1481932800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"973","award":["2015CB358700"],"award-info":[{"award-number":["2015CB358700"]}]},{"name":"NSFC China","award":["61272090, 61373024, 61422205, 61472198"],"award-info":[{"award-number":["61272090, 61373024, 61422205, 61472198"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00778-016-0449-y","type":"journal-article","created":{"date-parts":[[2016,12,17]],"date-time":"2016-12-17T13:33:32Z","timestamp":1481981612000},"page":"249-274","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["A unified framework for string similarity search with edit-distance constraint"],"prefix":"10.1007","volume":"26","author":[{"given":"Minghe","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong","family":"Deng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianhua","family":"Feng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,17]]},"reference":[{"key":"449_CR1","doi-asserted-by":"crossref","first-page":"e41","DOI":"10.1093\/nar\/gkr1246","volume":"40","author":"A Ahmadi","year":"2012","unstructured":"Ahmadi, A., Behm, A., Honnalli, N., Li, C., Weng, L., Xie, X.: Hobbes: optimized gram-based methods for efficient read alignment. Nucleic Acids Res. 40, e41 (2012)","journal-title":"Nucleic Acids Res."},{"key":"449_CR2","doi-asserted-by":"crossref","unstructured":"Bayardo, R.J., Ma, Y., Srikant, R.: Scaling up all pairs similarity search. In: WWW, pp. 131\u2013140 (2007)","DOI":"10.1145\/1242572.1242591"},{"key":"449_CR3","doi-asserted-by":"crossref","unstructured":"Behm, A., Li, C., Carey, M.J.: Answering approximate string queries on large data sets using external memory. In: ICDE, pp. 888\u2013899 (2011)","DOI":"10.1109\/ICDE.2011.5767856"},{"key":"449_CR4","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Ganti, V., Kaushik, R.: A primitive operator for similarity joins in data cleaning. In: ICDE (2006)","DOI":"10.1109\/ICDE.2006.9"},{"key":"449_CR5","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Kaushik, R.: Extending autocompletion to tolerate errors. In: SIGMOD Conference, pp. 707\u2013718 (2009)","DOI":"10.1145\/1559845.1559919"},{"key":"449_CR6","doi-asserted-by":"crossref","unstructured":"Deng, D., Li, G., Feng, J.: A pivotal prefix based filtering algorithm for string similarity search. In: SIGMOD Conference, pp. 673\u2013684 (2014)","DOI":"10.1145\/2588555.2593675"},{"issue":"1","key":"449_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00778-014-0367-9","volume":"24","author":"D Deng","year":"2015","unstructured":"Deng, D., Li, G., Feng, J., Duan, Y., Gong, Z.: A unified framework for approximate dictionary-based entity extraction. VLDB J. 24(1), 143\u2013167 (2015)","journal-title":"VLDB J."},{"key":"449_CR8","doi-asserted-by":"crossref","unstructured":"Deng, D., Li, G., Feng, J., Li, W.-S.: Top- $$k$$ k string similarity search with edit-distance constraints. In: ICDE, pp. 925\u2013936 (2013)","DOI":"10.1109\/ICDE.2013.6544886"},{"key":"449_CR9","doi-asserted-by":"crossref","unstructured":"Deng, D., Li, G., Hao, S., Wang, J., Feng, J.: Massjoin: a mapreduce-based method for scalable string similarity joins. In: ICDE, pp. 340\u2013351 (2014)","DOI":"10.1109\/ICDE.2014.6816663"},{"issue":"4","key":"449_CR10","first-page":"360","volume":"9","author":"D Deng","year":"2015","unstructured":"Deng, D., Li, G., Wen, H., Feng, J.: An efficient partition based method for exact set similarity joins. PVLDB 9(4), 360\u2013371 (2015)","journal-title":"PVLDB"},{"issue":"10","key":"449_CR11","first-page":"828","volume":"9","author":"D Deng","year":"2016","unstructured":"Deng, D., Li, G., Wen, H., Jagadish, H.V., Feng, J.: META: an efficient matching-based method for error-tolerant autocompletion. PVLDB 9(10), 828\u2013839 (2016)","journal-title":"PVLDB"},{"issue":"4","key":"449_CR12","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s00778-011-0252-8","volume":"21","author":"J Feng","year":"2012","unstructured":"Feng, J., Wang, J., Li, G.: Trie-join: a trie-based method for efficient string similarity joins. VLDB J. 21(4), 437\u2013461 (2012)","journal-title":"VLDB J."},{"key":"449_CR13","doi-asserted-by":"crossref","unstructured":"Gerdjikov, S., Mihov, S., Mitankin, P., Schulz, K.U.: Wallbreaker: overcoming the wall effect in similarity search. In:EDBT\/ICDT, pp. 366\u2013369 (2013)","DOI":"10.1145\/2457317.2457385"},{"key":"449_CR14","unstructured":"Guo, L., Shanmugasundaram, J., Beyer, K.S., Shekita, E.J.: Efficient inverted lists and query algorithms for structured value ranking in update-intensive relational databases. In: ICDE, pp. 298\u2013309 (2005)"},{"key":"449_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"1","key":"449_CR16","first-page":"201","volume":"1","author":"M Hadjieleftheriou","year":"2008","unstructured":"Hadjieleftheriou, M., Yu, X., Koudas, N., Srivastava, D.: Hashed samples: selectivity estimators for set similarity selection queries. PVLDB 1(1), 201\u2013212 (2008)","journal-title":"PVLDB"},{"key":"449_CR17","doi-asserted-by":"crossref","unstructured":"Ji, S., Li, G., Li, C., Feng, J.: Efficient interactive fuzzy keyword search. In: WWW (2009)","DOI":"10.1145\/1526709.1526760"},{"issue":"8","key":"449_CR18","first-page":"625","volume":"7","author":"Y Jiang","year":"2014","unstructured":"Jiang, Y., Li, G., Feng, J.: String similarity joins: an experimental evaluation. PVLDB 7(8), 625\u2013636 (2014)","journal-title":"PVLDB"},{"key":"449_CR19","doi-asserted-by":"crossref","unstructured":"Kim, Y., Shim, K.: Efficient top-k algorithms for approximate substring matching. In: SIGMOD Conference, pp. 385\u2013396 (2013)","DOI":"10.1145\/2463676.2465324"},{"key":"449_CR20","doi-asserted-by":"crossref","unstructured":"Li, C., Lu, J., Lu, Y.: Efficient merging and filtering algorithms for approximate string searches. In: ICDE, pp. 257\u2013266 (2008)","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"449_CR21","unstructured":"Li, C., Wang, B., Yang, X.: Vgram: improving performance of approximate queries on string collections using variable-length grams. In: VLDB, pp. 303\u2013314 (2007)"},{"key":"449_CR22","doi-asserted-by":"crossref","unstructured":"Li, G., Deng, D., Feng, J.: Faerie: efficient filtering algorithms for approximate dictionary-based entity extraction. In: SIGMOD Conference, pp. 529\u2013540 (2011)","DOI":"10.1145\/1989323.1989379"},{"issue":"3","key":"449_CR23","first-page":"253","volume":"5","author":"G Li","year":"2011","unstructured":"Li, G., Deng, D., Wang, J., Feng, J.: Pass-join: a partition-based method for similarity joins. PVLDB 5(3), 253\u2013264 (2011)","journal-title":"PVLDB"},{"issue":"2","key":"449_CR24","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1109\/TKDE.2011.148","volume":"25","author":"G Li","year":"2013","unstructured":"Li, G., Feng, J., Li, C.: Supporting search-as-you-type using SQL in databases. IEEE Trans. Knowl. Data Eng. 25(2), 461\u2013475 (2013)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"449_CR25","doi-asserted-by":"crossref","unstructured":"Li, G., He, J., Deng, D., Li, J.: Efficient similarity join and search on multi-attribute data. In: SIGMOD, pp. 1137\u20131151 (2015)","DOI":"10.1145\/2723372.2723733"},{"issue":"4","key":"449_CR26","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/s00778-011-0218-x","volume":"20","author":"G Li","year":"2011","unstructured":"Li, G., Ji, S., Li, C., Feng, J.: Efficient fuzzy full-text type-ahead search. VLDB J. 20(4), 617\u2013640 (2011)","journal-title":"VLDB J."},{"issue":"1","key":"449_CR27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.14778\/2047485.2047490","volume":"5","author":"E Mansour","year":"2011","unstructured":"Mansour, E., Allam, A., Skiadopoulos, S., Kalnis, P.: Era: Efficient serial and parallel suffix tree construction for very long strings. Proc. VLDB Endow. 5(1), 49\u201360 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"449_CR28","doi-asserted-by":"crossref","unstructured":"Qin, J., Wang, W., Lu, Y., Xiao, C., Lin, X.: Efficient exact edit similarity query processing with the asymmetric signature scheme. In: SIGMOD Conference, pp. 1033\u20131044 (2011)","DOI":"10.1145\/1989323.1989431"},{"key":"449_CR29","doi-asserted-by":"crossref","unstructured":"Sarawagi, S., Kirpal, A.: Efficient set joins on similarity predicates. In: SIGMOD Conference, pp. 743\u2013754 (2004)","DOI":"10.1145\/1007568.1007652"},{"issue":"4","key":"449_CR30","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"PH Sellers","year":"1980","unstructured":"Sellers, P.H.: The theory and computation of evolutionary distances: pattern recognition. J. Algorithms 1(4), 359\u2013373 (1980)","journal-title":"J. Algorithms"},{"key":"449_CR31","doi-asserted-by":"crossref","unstructured":"Siragusai, E., Weese, D., Reinert, K.: Fast and accurate read mapping with approximate seeds and multiple backtracking. Nucleic Acids Res. 41(7), e78 (2013)","DOI":"10.1093\/nar\/gkt005"},{"key":"449_CR32","doi-asserted-by":"crossref","unstructured":"Tomasic, A., Garcia-Molina, H., Shoens, K.A.: Incremental updates of inverted lists for text document retrieval. In: SIGMOD, pp. 289\u2013300 (1994)","DOI":"10.1145\/191839.191896"},{"issue":"1","key":"449_CR33","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1145\/2627692.2627706","volume":"43","author":"S Wandelt","year":"2014","unstructured":"Wandelt, S., Deng, D., Gerdjikov, S., Mishra, S., Mitankin, P., Patil, M., Siragusa, E., Tiskin, A., Wang, W., Wang, J., Leser, U.: State-of-the-art in string similarity search and join. SIGMOD Rec. 43(1), 64\u201376 (2014)","journal-title":"SIGMOD Rec."},{"key":"449_CR34","doi-asserted-by":"crossref","unstructured":"Wang, J., Li, G., Deng, D., Zhang, Y., Feng, J.: Two birds with one stone: an efficient hierarchical framework for top- $$k$$ k and threshold-based string similarity search. In: ICDE (2015)","DOI":"10.1109\/ICDE.2015.7113311"},{"key":"449_CR35","doi-asserted-by":"crossref","unstructured":"Wang, J., Li, G., Feng, J.: Trie-join: efficient trie-based string similarity joins with edit-distance constraints. PVLDB 3(1), 1219\u20131230 (2010)","DOI":"10.14778\/1920841.1920992"},{"key":"449_CR36","doi-asserted-by":"crossref","unstructured":"Wang, J., Li, G., Feng, J.: Fast-join: An efficient method for fuzzy token matching based string similarity join. In: ICDE, pp. 458\u2013469 (2011)","DOI":"10.1109\/ICDE.2011.5767865"},{"key":"449_CR37","doi-asserted-by":"crossref","unstructured":"Wang, J., Li, G., Feng, J.: Can we beat the prefix filtering? An adaptive framework for similarity join and search. In: SIGMOD Conference, pp. 85\u201396 (2012)","DOI":"10.1145\/2213836.2213847"},{"key":"449_CR38","doi-asserted-by":"crossref","unstructured":"Wang, W., Xiao, C., Lin, X., Zhang, C.: Efficient approximate entity extraction with edit distance constraints. In: SIGMOD Conference, (2009)","DOI":"10.1145\/1559845.1559925"},{"key":"449_CR39","first-page":"1","volume":"7","author":"X Wang","year":"2014","unstructured":"Wang, X., Ding, X., Tung, A.K.H., Zhang, Z.: Efficient and effective knn sequence search with approximate n-grams. PVLDB 7, 1\u201312 (2014)","journal-title":"PVLDB"},{"issue":"6","key":"449_CR40","first-page":"373","volume":"6","author":"C Xiao","year":"2013","unstructured":"Xiao, C., Qin, J., Wang, W., Ishikawa, Y., Tsuda, K., Sadakane, K.: Efficient error-tolerant query autocompletion. PVLDB 6(6), 373\u2013384 (2013)","journal-title":"PVLDB"},{"issue":"1","key":"449_CR41","first-page":"933","volume":"1","author":"C Xiao","year":"2008","unstructured":"Xiao, C., Wang, W., Lin, X.: Ed-join: an efficient algorithm for similarity joins with edit distance constraints. PVLDB 1(1), 933\u2013944 (2008)","journal-title":"PVLDB"},{"key":"449_CR42","doi-asserted-by":"crossref","unstructured":"Xiao, C., Wang, W., Lin, X., Yu, J.X.: Efficient similarity joins for near duplicate detection. In: WWW, pp. 131\u2013140 (2008)","DOI":"10.1145\/1367497.1367516"},{"key":"449_CR43","doi-asserted-by":"crossref","unstructured":"Yang, Z., Yu, J., Kitsuregawa, M.: Fast algorithms for top-k approximate string matching. In: AAAI (2010)","DOI":"10.1609\/aaai.v24i1.7527"},{"issue":"3","key":"449_CR44","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11704-015-5900-5","volume":"10","author":"M Yu","year":"2016","unstructured":"Yu, M., Li, G., Deng, D., Feng, J.: String similarity search and join: a survey. Front. Comput. Sci. 10(3), 399\u2013417 (2016)","journal-title":"Front. Comput. Sci."},{"key":"449_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Hadjieleftheriou, M., Ooi, B.C., Srivastava, D.: Bed-tree: an all-purpose index structure for string similarity search based on edit distance. In: SIGMOD Conference, pp. 915\u2013926 (2010)","DOI":"10.1145\/1807167.1807266"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-016-0449-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-016-0449-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-016-0449-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T09:53:01Z","timestamp":1692611581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-016-0449-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,17]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["449"],"URL":"https:\/\/doi.org\/10.1007\/s00778-016-0449-y","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,17]]}}}