{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:17:33Z","timestamp":1768317453515,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T00:00:00Z","timestamp":1666224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T00:00:00Z","timestamp":1666224000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100011958","name":"Danmarks Frie Forskningsfond","doi-asserted-by":"publisher","award":["8021-002498"],"award-info":[{"award-number":["8021-002498"]}],"id":[{"id":"10.13039\/501100011958","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00453-022-01051-6","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T12:04:52Z","timestamp":1666267492000},"page":"879-901","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Gapped Indexing for Consecutive Occurrences"],"prefix":"10.1007","volume":"85","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max Rish\u00f8j","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1078-4075","authenticated-orcid":false,"given":"Teresa Anna","family":"Steiner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,20]]},"reference":[{"key":"1051_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Proceedings of the 24th ICALP, pp. 270\u2013280 (1997)","DOI":"10.1007\/3-540-63165-8_184"},{"key":"1051_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J., Thorup, M.: Maintaining center and median in dynamic trees. In: Proceedings of the 7th SWAT, pp. 46\u201356 (2000)","DOI":"10.1007\/3-540-44985-X_6"},{"key":"1051_CR3","unstructured":"Alstrup, S., Rauhe, T.: Improved labeling scheme for ancestor queries. In: Proceedings of the 13th SODA, pp. 947\u2013953 (2002)"},{"key":"1051_CR4","doi-asserted-by":"crossref","unstructured":"Amir, A., Chan, T.M., Lewenstein, M., Lewenstein, N.: On hardness of jumbled indexing. In: Proceedings of the 41st ICALP, pp. 114\u2013125 (2014)","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"1051_CR5","unstructured":"Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap: essentially optimal algorithms for online dictionary matching with one gap. In: Proceedings of the 27th ISAAC, pp. 12:1\u201312:12 (2016)"},{"key":"1051_CR6","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Pizzi, C., Satta, G.: Optimal discovery of subword associations in strings. In: Proceedings of the 7th DS, pp. 270\u2013277 (2004)","DOI":"10.1007\/978-3-540-30214-8_21"},{"key":"1051_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1186\/1748-7188-6-5","volume":"6","author":"A Apostolico","year":"2011","unstructured":"Apostolico, A., Pizzi, C., Ukkonen, E.: Efficient algorithms for the discovery of gapped factors. Algorithms Mol. Biol. 6, 5 (2011)","journal-title":"Algorithms Mol. Biol."},{"issue":"2","key":"1051_CR8","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.jda.2007.02.003","volume":"7","author":"A Apostolico","year":"2009","unstructured":"Apostolico, A., Satta, G.: Discovering subword associations in strings in time linear in the output size. J. Discrete Algorithms 7(2), 227\u2013238 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"1051_CR9","doi-asserted-by":"crossref","unstructured":"Bader, J., Gog, S., Petri, M.: Practical variable length gap pattern matching. In: Proceedings of the 15th SEA, pp. 1\u201316 (2016)","DOI":"10.1007\/978-3-319-38851-9_1"},{"issue":"3","key":"1051_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1978782.1978793","volume":"7","author":"P Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: The tree inclusion problem: in linear space and faster. ACM Trans. Algorithms 7(3), 1\u201347 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1051_CR11","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/s00453-012-9733-4","volume":"69","author":"P Bille","year":"2014","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring range reporting. Algorithmica 69(2), 384\u2013396 (2014)","journal-title":"Algorithmica"},{"key":"1051_CR12","unstructured":"Bille, P., G\u00f8rtz, I.L., Pedersen, M.R., Rotenberg, E., Steiner, T.A.: String indexing for top-$$k$$ close consecutive occurrences. In: Proceedings of the 40th FSTTCS, pp. 14:1\u201314:17 (2020)"},{"key":"1051_CR13","unstructured":"Bille, P., G\u00f8rtz, I.L., Pedersen, M.R., Steiner, T.A.: Gapped indexing for consecutive occurrences. In: Proceedings of the 32nd CPM, pp. 10:1\u201310:19 (2021)"},{"issue":"1","key":"1051_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00224-013-9498-4","volume":"55","author":"P Bille","year":"2014","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Vind, S.: String indexing for patterns with wildcards. Theory Comput. Syst. 55(1), 41\u201360 (2014)","journal-title":"Theory Comput. Syst."},{"key":"1051_CR15","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Wind, D.K.: String matching with variable length gaps. Theor. Comput. Sci. 443 (2012). Announced at SPIRE (2010)","DOI":"10.1016\/j.tcs.2012.03.029"},{"key":"1051_CR16","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2018.06.029","volume":"746","author":"S Biswas","year":"2018","unstructured":"Biswas, S., Ganguly, A., Shah, R., Thankachan, S.V.: Ranked document retrieval for multiple patterns. Theor. Comput. Sci. 746, 98\u2013111 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"1051_CR17","unstructured":"Bucher, P., Bairoch, A.: A generalized profile syntax for biomolecular sequence motifs and its function in automatic sequence interpretation. In: Proceedings of the 2nd ISMB, pp. 53\u201361 (1994)"},{"key":"1051_CR18","doi-asserted-by":"crossref","unstructured":"C\u00e1ceres, M., Puglisi, S.J., Zhukova, B.: Fast indexes for gapped pattern matching. In: Proceedings of the 46th SOFSEM, pp. 493\u2013504 (2020)","DOI":"10.1007\/978-3-030-38919-2_40"},{"issue":"40\u201342","key":"1051_CR19","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40\u201342), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1051_CR20","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0022-0000(03)00028-X","volume":"66","author":"P Ferragina","year":"2003","unstructured":"Ferragina, P., Koudas, N., Muthukrishnan, S., Srivastava, D.: Two-dimensional substring indexing. J. Comput. Syst. Sci. 66(4), 763\u2013774 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1051_CR21","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"GN Frederickson","year":"1997","unstructured":"Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and $$k$$ smallest spanning trees. SIAM J. Comput. 26(2), 484\u2013538 (1997)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1051_CR22","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$o(1)$$ worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"1051_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10791-008-9054-z","volume":"11","author":"K Fredriksson","year":"2008","unstructured":"Fredriksson, K., Grabowski, S.: Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Inf. Retr. 11(4), 335\u2013357 (2008)","journal-title":"Inf. Retr."},{"key":"1051_CR24","doi-asserted-by":"crossref","unstructured":"Goldstein, I., Kopelowitz, T., Lewenstein, M., Porat, E.: Conditional lower bounds for space\/time tradeoffs. In: Proceedings of the 15th WADS, pp. 421\u2013436. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"1051_CR25","doi-asserted-by":"crossref","unstructured":"Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: Proceedings of the 10th SEA, pp. 76\u201387 (2011)","DOI":"10.1007\/978-3-642-20662-7_7"},{"issue":"1","key":"1051_CR26","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1093\/nar\/27.1.215","volume":"27","author":"K Hofmann","year":"1999","unstructured":"Hofmann, K., Bucher, P., Falquet, L., Bairoch, A.: The PROSITE database, its status in 1999. Nucleic Acids Res. 27(1), 215\u2013219 (1999)","journal-title":"Nucleic Acids Res."},{"key":"1051_CR27","doi-asserted-by":"crossref","unstructured":"Hon, W., Patil, M., Shah, R., Thankachan, S.V., Vitter, J.S.: Indexes for document retrieval with relevance. In: Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 351\u2013362 (2013)","DOI":"10.1007\/978-3-642-40273-9_22"},{"key":"1051_CR28","doi-asserted-by":"crossref","unstructured":"Hon, W., Thankachan, S.V., Shah, R., Vitter, J.S.: Faster compressed top-k document retrieval. In: Proceedings of the 23rd DCC, pp. 341\u2013350 (2013)","DOI":"10.1109\/DCC.2013.42"},{"issue":"4","key":"1051_CR29","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.jda.2010.08.003","volume":"8","author":"WK Hon","year":"2010","unstructured":"Hon, W.K., Patil, M., Shah, R., Wu, S.B.: Efficient index for retrieving top-k most frequent documents. J. Discrete Algorithms 8(4), 402\u2013417 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"1051_CR30","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Shah, R., Thankachan, S.V., Vitter, J.S.: Space-efficient frameworks for top-k string retrieval. J. ACM 61(2), 1\u201336 (2014). Announced at 50th FOCS","DOI":"10.1145\/2590774"},{"issue":"1","key":"1051_CR31","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-007-9141-3","volume":"55","author":"CS Iliopoulos","year":"2009","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Indexing factors with gaps. Algorithmica 55(1), 60\u201370 (2009)","journal-title":"Algorithmica"},{"key":"1051_CR32","doi-asserted-by":"crossref","unstructured":"Keller, O., Kopelowitz, T., Lewenstein, M.: Range non-overlapping indexing and successive list indexing. In: Proceedings of the 11th WADS, pp. 625\u2013636 (2007)","DOI":"10.1007\/978-3-540-73951-7_54"},{"key":"1051_CR33","unstructured":"Kopelowitz, T., Krauthgamer, R.: Color-distance oracles and snippets. In: Grossi, R., Lewenstein, M. (Eds.) Proceedings of the 27th CPM, pp. 24:1\u201324:10 (2016)"},{"key":"1051_CR34","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3sum conjecture. In: Proceedings of the 27th SODA, pp. 1272\u20131287 (2016)","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"1051_CR35","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2015.03.026","volume":"582","author":"KG Larsen","year":"2015","unstructured":"Larsen, K.G., Munro, J.I., Nielsen, J.S., Thankachan, S.V.: On hardness of several string indexing problems. Theor. Comput. Sci. 582, 74\u201382 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"1051_CR36","doi-asserted-by":"crossref","unstructured":"Lewenstein, M.: Indexing with gaps. In: Proceedings of the 18th SPIRE, pp. 135\u2013143 (2011)","DOI":"10.1007\/978-3-642-24583-1_14"},{"issue":"3","key":"1051_CR37","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1093\/bioinformatics\/9.3.299","volume":"9","author":"G Mehldau","year":"1993","unstructured":"Mehldau, G., Myers, G.: A system for pattern matching applications on biosequences. Bioinformatics 9(3), 299\u2013314 (1993)","journal-title":"Bioinformatics"},{"key":"1051_CR38","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Navarro, G., Nielsen, J.S., Shah, R., Thankachan, S.V.: Top-k term-proximity in succinct space. Algorithmica 78(2), 379\u2013393 (2017). Announced at 25th ISAAC","DOI":"10.1007\/s00453-016-0167-2"},{"key":"1051_CR39","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2019.10.008","volume":"812","author":"JI Munro","year":"2020","unstructured":"Munro, J.I., Navarro, G., Shah, R., Thankachan, S.V.: Ranked document selection. Theor. Comput. Sci. 812, 149\u2013159 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1051_CR40","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1089\/cmb.1996.3.33","volume":"3","author":"EW Myers","year":"1992","unstructured":"Myers, E.W.: Approximate matching of network expressions with spacers. J. Comput. Biol. 3(1), 33\u201351 (1992)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"1051_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2535933","volume":"46","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 1\u201347 (2014)","journal-title":"ACM Comput. Surv."},{"key":"1051_CR42","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Time-optimal top-k document retrieval. SIAM J. Comput. 46(1), 80\u2013113 (2017). Announced at 23rd SODA","DOI":"10.1137\/140998949"},{"issue":"6","key":"1051_CR43","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1089\/106652703322756140","volume":"10","author":"G Navarro","year":"2003","unstructured":"Navarro, G., Raffinot, M.: Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. J. Comput. Biol. 10(6), 903\u2013923 (2003)","journal-title":"J. Comput. Biol."},{"key":"1051_CR44","doi-asserted-by":"crossref","unstructured":"Navarro, G., Thankachan, S.V.: New space\/time tradeoffs for top-k document retrieval on sequences. Theor. Comput. Sci. 542, 83\u201397 (2014). Announced at 20th SPIRE","DOI":"10.1016\/j.tcs.2014.05.005"},{"key":"1051_CR45","doi-asserted-by":"crossref","unstructured":"Navarro, G., Thankachan, S.V.: Reporting consecutive substring occurrences under bounded gap constraints. Theor. Comput. Sci. 638, 108\u2013111 (2016). Announced at 26th CPM","DOI":"10.1016\/j.tcs.2016.02.005"},{"key":"1051_CR46","doi-asserted-by":"crossref","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Proceedings of the 13th SWAT, pp. 271\u2013282 (2012)","DOI":"10.1007\/978-3-642-31155-0_24"},{"key":"1051_CR47","doi-asserted-by":"crossref","unstructured":"Shah, R., Sheng, C., Thankachan, S.V., Vitter, J.S.: Top-k document retrieval in external memory. In: Proceedings of the 21st ESA, pp. 803\u2013814 (2013)","DOI":"10.1007\/978-3-642-40450-4_68"},{"issue":"12","key":"1051_CR48","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1016\/j.ipl.2013.03.012","volume":"113","author":"D Tsur","year":"2013","unstructured":"Tsur, D.: Top-k document retrieval in optimal space. Inf. Process. Lett. 113(12), 440\u2013443 (2013)","journal-title":"Inf. Process. Lett."},{"key":"1051_CR49","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th FOCS, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"1051_CR50","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3.","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett. 17(2), 81\u201384 (1983). https:\/\/doi.org\/10.1016\/0020-0190(83)90075-3.","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1051_CR51","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.ipl.2015.09.002","volume":"116","author":"G Zhou","year":"2016","unstructured":"Zhou, G.: Two-dimensional range successor in optimal time and almost linear space. Inf. Process. Lett. 116(2), 171\u2013174 (2016)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01051-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01051-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01051-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T07:14:25Z","timestamp":1728198865000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01051-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,20]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1051"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01051-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,20]]},"assertion":[{"value":"16 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}