{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T08:19:03Z","timestamp":1769156343898,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T00:00:00Z","timestamp":1670284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T00:00:00Z","timestamp":1670284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["World Wide Web"],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s11280-022-01128-w","type":"journal-article","created":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T05:02:35Z","timestamp":1670302955000},"page":"1967-2001","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hierarchical filtering: improving similar substring matching under edit distance"],"prefix":"10.1007","volume":"26","author":[{"given":"Tao","family":"Qiu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuanyu","family":"Zong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaochun","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,6]]},"reference":[{"issue":"6","key":"1128_CR1","doi-asserted-by":"publisher","first-page":"e41","DOI":"10.1093\/nar\/gkr1246","volume":"40","author":"A Ahmadi","year":"2011","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(6), e41\u2013e41 (2011). https:\/\/doi.org\/10.1093\/nar\/gkr1246https:\/\/doi.org\/10.1093\/nar\/gkr1246","journal-title":"Nucleic Acids Res."},{"key":"1128_CR2","doi-asserted-by":"publisher","unstructured":"Kim, J., Li, C., Xie, X.: Hobbes3: dynamic generation of variable-length signatures for efficient approximate subsequence mappings. In: ICDE, IEEE, pp. 169\u2013180. https:\/\/doi.org\/10.1109\/ICDE.2016.7498238https:\/\/doi.org\/10.1109\/ICDE.2016.7498238(2016)","DOI":"10.1109\/ICDE.2016.7498238 10.1109\/ICDE.2016.7498238"},{"key":"1128_CR3","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.ins.2013.04.037","volume":"244","author":"Y Kim","year":"2013","unstructured":"Kim, Y., Park, H., Shim, K., Woo, K.G.: Efficient processing of substring match queries with inverted variable-length gram indexes. Inform. Sci. 244, 119\u2013141 (2013). https:\/\/doi.org\/10.1016\/j.ins.2013.04.037https:\/\/doi.org\/10.1016\/j.ins.2013.04.037","journal-title":"Inform. Sci."},{"issue":"14","key":"1128_CR4","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows\u2013wheeler transform. Bioinformatics 25(14), 1754\u20131760 (2009). https:\/\/doi.org\/10.1093\/bioinformatics\/btp324","journal-title":"Bioinformatics"},{"key":"1128_CR5","doi-asserted-by":"publisher","unstructured":"Li, C., Lu, J., Lu, Y.: Efficient merging and filtering algorithms for approximate string searches. In: ICDE, IEEE, pp. 257\u2013266. https:\/\/doi.org\/10.1109\/ICDE.2008.4497434 (2008)","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"1128_CR6","doi-asserted-by":"publisher","unstructured":"Wang, J., Li, G., Deng, D., Zhang, Y., Feng, J.: Two birds with one stone: an efficient hierarchical framework for top-k and threshold-based string similarity search. In: ICDE, IEEE, pp. 519\u2013530. https:\/\/doi.org\/10.1109\/ICDE.2015.7113311 (2015)","DOI":"10.1109\/ICDE.2015.7113311"},{"key":"1128_CR7","doi-asserted-by":"publisher","unstructured":"Wang, J., Yang, X., Wang, B., Liu, C.: An adaptive approach of approximate substring matching. In: DASFAA, Springer, pp. 501\u2013516. https:\/\/doi.org\/10.1007\/978-3-319-32025-0_31 (2016)","DOI":"10.1007\/978-3-319-32025-0_31"},{"issue":"3","key":"1128_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2508020.2508023","volume":"38","author":"J Qin","year":"2013","unstructured":"Qin, J., Wang, W., Xiao, C., Lu, Y., Lin, X., Wang, H.: Asymmetric signature schemes for efficient exact edit similarity query processing. ACM Trans. Database Syst. 38(3), 1\u201344 (2013). https:\/\/doi.org\/10.1145\/2508020.2508023","journal-title":"ACM Trans. Database Syst."},{"issue":"9","key":"1128_CR9","doi-asserted-by":"publisher","first-page":"1928","DOI":"10.1109\/TKDE.2017.2687460","volume":"29","author":"J Wang","year":"2017","unstructured":"Wang, J., Yang, X., Wang, B., Liu, C.: Ls-join: local similarity join on string collections. IEEE Trans. Knowl. Data Eng. 29(9), 1928\u20131942 (2017). https:\/\/doi.org\/10.1109\/TKDE.2017.2687460","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"1128_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1186\/1471-2105-15-42","volume":"15","author":"J Kim","year":"2014","unstructured":"Kim, J., Li, C., Xie, X.: Improving read mapping using additional prefix grams. BMC Bioinform. 15(1), 42 (2014). https:\/\/doi.org\/10.1186\/1471-2105-15-42","journal-title":"BMC Bioinform."},{"key":"1128_CR11","doi-asserted-by":"crossref","unstructured":"Kim, Y., Shim, K.: Efficient top-k algorithms for approximate substring matching. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data, pp. 385\u2013396 (2013)","DOI":"10.1145\/2463676.2465324"},{"issue":"1","key":"1128_CR12","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E Ukkonen","year":"1992","unstructured":"Ukkonen, E.: Approximate string-matching with q-grams and maximal matches. Theo. Comput. Sci. 92(1), 191\u2013211 (1992). https:\/\/doi.org\/10.1016\/0304-3975(92)90143-4","journal-title":"Theo. Comput. Sci."},{"issue":"3","key":"1128_CR13","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G Myers","year":"1999","unstructured":"Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM 46(3), 395\u2013415 (1999). https:\/\/doi.org\/10.1145\/316542.316550","journal-title":"J. ACM"},{"issue":"1","key":"1128_CR14","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1186\/s12859-015-0626-9","volume":"16","author":"H Cheng","year":"2015","unstructured":"Cheng, H., Jiang, H., Yang, J., Xu, Y., Shang, Y.: Bitmapper: an efficient all-mapper based on bit-vector computing. BMC Bioinform. 16 (1), 192 (2015). https:\/\/doi.org\/10.1186\/s12859-015-0626-9","journal-title":"BMC Bioinform."},{"issue":"3","key":"1128_CR15","doi-asserted-by":"publisher","first-page":"253","DOI":"10.14778\/2078331.2078340","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). https:\/\/doi.org\/10.14778\/2078331.2078340","journal-title":"PVLDB"},{"key":"1128_CR16","doi-asserted-by":"publisher","unstructured":"Yang, X., Wang, B., Li, C., Wang, J., Xie, X.: Efficient direct search on compressed genomic data. In: ICDE, IEEE, pp. 961\u2013972. https:\/\/doi.org\/10.1109\/ICDE.2013.6544889 (2013)","DOI":"10.1109\/ICDE.2013.6544889"},{"key":"1128_CR17","doi-asserted-by":"publisher","unstructured":"Chen, C., Qin, J., Wang, W.: On gapped set intersection size estimation. In: CIKM, ACM, pp. 1351\u20131360. https:\/\/doi.org\/10.1145\/2806416.2806438 (2015)","DOI":"10.1145\/2806416.2806438"},{"issue":"7319","key":"1128_CR18","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1038\/nature09534","volume":"467","author":"TGP Consortium","year":"2010","unstructured":"Consortium, T.G.P.: A map of human genome variation from population-scale sequencing. Nature 467(7319)), 1061\u20131073 (2010). https:\/\/doi.org\/10.1038\/nature09534","journal-title":"Nature"},{"issue":"20","key":"1128_CR19","doi-asserted-by":"publisher","first-page":"2592","DOI":"10.1093\/bioinformatics\/bts505","volume":"28","author":"D Weese","year":"2012","unstructured":"Weese, D., Holtgrewe, M., Reinert, K.: Razers 3: faster, fully sensitive read mapping. Bioinformatics 28(20), 2592\u20132599 (2012). https:\/\/doi.org\/10.1093\/bioinformatics\/bts505","journal-title":"Bioinformatics"},{"issue":"3","key":"1128_CR20","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Molecular Bio. 215(3), 403\u2013410 (1990). https:\/\/doi.org\/10.1016\/S0022-2836(05)80360-2","journal-title":"J. Molecular Bio."},{"key":"1128_CR21","doi-asserted-by":"publisher","unstructured":"Qiu, T., Yang, X., Wang, B., Han, Y., Wang, S.: Efficient approximate subsequence matching using hybrid signatures. In: DASFAA, Springer, pp. 600\u2013609. https:\/\/doi.org\/10.1007\/978-3-319-91452-7_39 (2018)","DOI":"10.1007\/978-3-319-91452-7_39"},{"key":"1128_CR22","doi-asserted-by":"publisher","unstructured":"Yang, X., Wang, B., Li, C.: Cost-based variable-length-gram selection for string collections to support approximate queries efficiently. In: SIGMOD, ACM, pp. 353\u2013364. https:\/\/doi.org\/10.1145\/1376616.1376655 (2008)","DOI":"10.1145\/1376616.1376655"},{"issue":"7","key":"1128_CR23","doi-asserted-by":"publisher","first-page":"e78","DOI":"10.1093\/nar\/gkt005","volume":"41","author":"E Siragusa","year":"2013","unstructured":"Siragusa, E., Weese, D., Reinert, K.: Fast and accurate read mapping with approximate seeds and multiple backtracking. Nucleic Acids Res. 41(7), e78\u2013e78 (2013). https:\/\/doi.org\/10.1093\/nar\/gkt005","journal-title":"Nucleic Acids Res."},{"key":"1128_CR24","doi-asserted-by":"publisher","unstructured":"Hanhan, R., Garz\u00f3n, E., Jahshan, Z., Teman, A., Lanuzza, M., Yavits, L.: Edam: edit distance tolerant approximate matching content addressable memory. In: ISCA, ACM, pp. 495\u2014-507. https:\/\/doi.org\/10.1145\/3470496.3527424 (2022)","DOI":"10.1145\/3470496.3527424"},{"issue":"6","key":"1128_CR25","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","volume":"24","author":"TW Lam","year":"2008","unstructured":"Lam, T.W., Sung, W.-K., Tam, S.-L., Wong, C.-K., Yiu, S.-M.: Compressed indexing and local alignment of dna. Bioinformatics 24(6), 791\u2013797 (2008). https:\/\/doi.org\/10.1093\/bioinformatics\/btn032","journal-title":"Bioinformatics"},{"issue":"5","key":"1128_CR26","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with burrows\u2013wheeler transform. Bioinformatics 26(5), 589\u2013595 (2010). https:\/\/doi.org\/10.1093\/bioinformatics\/btp698","journal-title":"Bioinformatics"},{"issue":"11","key":"1128_CR27","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.14778\/2350229.2350265","volume":"5","author":"X Yang","year":"2012","unstructured":"Yang, X., Liu, H., Wang, B.: Alae: accelerating local alignment with affine gap exactly in biosequence databases. PVLDB 5(11), 1507\u20131518 (2012). https:\/\/doi.org\/10.14778\/2350229.2350265","journal-title":"PVLDB"},{"key":"1128_CR28","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, IEEE, pp. 390\u2013398. https:\/\/doi.org\/10.1109\/SFCS.2000.892127 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"1128_CR29","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Tech. Rep. (1994)"},{"issue":"11","key":"1128_CR30","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1089\/cmb.2011.0185","volume":"18","author":"D Newkirk","year":"2011","unstructured":"Newkirk, D., Biesinger, J., Chon, A., Yokomori, K., Xie, X.: Arem: aligning short reads from chip-sequencing by expectation maximization. J. Comput. Biol. 18(11), 1495\u20131505 (2011). https:\/\/doi.org\/10.1089\/cmb.2011.0185","journal-title":"J. Comput. Biol."},{"issue":"1","key":"1128_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1038\/nmeth.2251","volume":"10","author":"A Roberts","year":"2013","unstructured":"Roberts, A., Pachter, L.: Streaming fragment assignment for real-time analysis of sequencing experiments. Nat. Methods 10(1), 71\u201373 (2013). https:\/\/doi.org\/10.1038\/nmeth.2251","journal-title":"Nat. Methods"},{"issue":"3","key":"1128_CR32","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Bio. 10(3), R25 (2009). https:\/\/doi.org\/10.1186\/gb-2009-10-3-r25","journal-title":"Genome Bio."},{"issue":"4","key":"1128_CR33","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with bowtie 2. Nat. Methods 9(4), 357\u2013359 (2012). https:\/\/doi.org\/10.1038\/nmeth.1923","journal-title":"Nat. Methods"},{"issue":"1","key":"1128_CR34","doi-asserted-by":"publisher","first-page":"933","DOI":"10.14778\/1453856.1453957","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). https:\/\/doi.org\/10.14778\/1453856.1453957","journal-title":"PVLDB"},{"key":"1128_CR35","doi-asserted-by":"publisher","unstructured":"Echihabi, K., Zoumpatianos, K., Palpanas, T.: High-dimensional similarity search for scalable data science. In: ICDE, IEEE, pp. 2369\u20132372. https:\/\/doi.org\/10.1109\/ICDE51399.2021.00268 (2021)","DOI":"10.1109\/ICDE51399.2021.00268"},{"issue":"1","key":"1128_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1186810.1186812","volume":"3","author":"G Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Trans. Alg. 3(1), 1\u201319 (2007). https:\/\/doi.org\/10.1145\/1186810.1186812","journal-title":"ACM Trans. Alg."},{"issue":"6","key":"1128_CR37","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1093\/comjnl\/bxaa193","volume":"65","author":"FJ Fiori","year":"2021","unstructured":"Fiori, F.J., Pakal\u00e9n, W., Tarhio, J.: Approximate string matching with SIMD. Comput. J. 65(6), 1472\u20131488 (2021). https:\/\/doi.org\/10.1093\/comjnl\/bxaa193","journal-title":"Comput. J."},{"key":"1128_CR38","doi-asserted-by":"publisher","unstructured":"Song, G., Shim, K., Lee, H.: Substring similarity search with synonyms. In: ICDE, IEEE, pp. 2003\u20132008. https:\/\/doi.org\/10.1109\/ICDE51399.2021.00191 (2021)","DOI":"10.1109\/ICDE51399.2021.00191"},{"issue":"3","key":"1128_CR39","doi-asserted-by":"publisher","first-page":"102919","DOI":"10.1016\/j.ipm.2022.102919","volume":"59","author":"Z Zhang","year":"2022","unstructured":"Zhang, Z., Pun, C.-M.: Learning ordinal constraint binary codes for fast similarity search. Inf. Process. Manag. 59(3), 102919 (2022). https:\/\/doi.org\/10.1016\/j.ipm.2022.102919","journal-title":"Inf. Process. Manag."},{"issue":"6","key":"1128_CR40","doi-asserted-by":"publisher","first-page":"102074","DOI":"10.1016\/j.ipm.2019.102074","volume":"56","author":"Z Meng","year":"2019","unstructured":"Meng, Z., Shen, H.: Fast top-k similarity search in large dynamic attributed networks. Inf. Process. Manag. 56(6), 102074 (2019). https:\/\/doi.org\/10.1016\/j.ipm.2019.102074","journal-title":"Inf. Process. Manag."},{"issue":"1","key":"1128_CR41","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.ipm.2012.07.003","volume":"49","author":"M Lu","year":"2013","unstructured":"Lu, M., Huang, Y., Xie, M., Liu, J.: Rank hash similarity for fast similarity search. Inf. Process. Manag. 49(1), 158\u2013168 (2013). https:\/\/doi.org\/10.1016\/j.ipm.2012.07.003","journal-title":"Inf. Process. Manag."},{"key":"1128_CR42","doi-asserted-by":"publisher","unstructured":"Yuan, H., Li, G.: Distributed in-memory trajectory similarity search and join on road network. In: ICDE, IEEE, pp. 1262\u20131273. https:\/\/doi.org\/10.1109\/ICDE.2019.00115 (2019)","DOI":"10.1109\/ICDE.2019.00115"},{"issue":"13","key":"1128_CR43","doi-asserted-by":"publisher","first-page":"2236","DOI":"10.14778\/3275366.3284968","volume":"11","author":"M Linardi","year":"2018","unstructured":"Linardi, M., Palpanas, T.: Scalable, variable-length similarity search in data series: the ulisse approach. PVLDB 11(13), 2236\u20132248 (2018). https:\/\/doi.org\/10.14778\/3275366.3284968","journal-title":"PVLDB"}],"container-title":["World Wide Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-022-01128-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11280-022-01128-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-022-01128-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T14:43:39Z","timestamp":1690382619000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11280-022-01128-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,6]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1128"],"URL":"https:\/\/doi.org\/10.1007\/s11280-022-01128-w","relation":{},"ISSN":["1386-145X","1573-1413"],"issn-type":[{"value":"1386-145X","type":"print"},{"value":"1573-1413","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,6]]},"assertion":[{"value":"21 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Competing interests"}}]}}