{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:52Z","timestamp":1759638112694,"version":"3.41.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,5,27]],"date-time":"2016-05-27T00:00:00Z","timestamp":1464307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00453-016-0167-2","type":"journal-article","created":{"date-parts":[[2016,5,27]],"date-time":"2016-05-27T14:04:07Z","timestamp":1464357847000},"page":"379-393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Top-k Term-Proximity in Succinct Space"],"prefix":"10.1007","volume":"78","author":[{"given":"J. Ian","family":"Munro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper Sindahl","family":"Nielsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,27]]},"reference":[{"key":"167_CR1","volume-title":"Modern Information Retrieval","author":"R Baeza-Yates","year":"2011","unstructured":"Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval, 2nd edn. Addison-Wesley, Reading (2011)","edition":"2"},{"key":"167_CR2","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Proceedings of the 19th ESA, pp. 748\u2013759 (2011)","DOI":"10.1007\/978-3-642-23719-5_63"},{"key":"167_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jda.2012.07.005","volume":"18","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval. J. Discrete Algorithms 18, 3\u201313 (2013)","journal-title":"J. Discrete Algorithms"},{"issue":"22","key":"167_CR4","doi-asserted-by":"publisher","first-page":"4828","DOI":"10.1093\/nar\/22.22.4828","volume":"22","author":"G Benson","year":"1994","unstructured":"Benson, G., Waterman, M.: A fast method for fast database search for all $$k$$ k -nucleotide repeats. Nucleic Acids Res. 22(22), 4828\u20134836 (1994)","journal-title":"Nucleic Acids Res."},{"key":"167_CR5","doi-asserted-by":"crossref","unstructured":"Broschart, A., Schenkel, R.: Index tuning for efficient proximity-enhanced query processing. In: INEX, pp. 213\u2013217 (2009)","DOI":"10.1007\/978-3-642-14556-8_22"},{"key":"167_CR6","volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","author":"S B\u00fcttcher","year":"2010","unstructured":"B\u00fcttcher, S., Clarke, C.L.A., Cormack, G.: Information Retrieval: Implementing and Evaluating Search Engines. MIT Press, Cambridge (2010)"},{"key":"167_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"2","key":"167_CR8","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a new data structure for string search in external memory and its applications. J. ACM. 46(2), 236\u2013280 (1999)","journal-title":"J. ACM."},{"key":"167_CR9","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms 3(2), Art. No. 20 (2007)","DOI":"10.1145\/1240233.1240243"},{"key":"167_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2011.12.002","volume":"426\u2013427","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theor. Comput. Sci. 426\u2013427, 25\u201341 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"167_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"167_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jda.2012.09.002","volume":"17","author":"W-K Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On position restricted substring searching in succinct space. J. Discrete Algorithms 17, 109\u2013114 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"167_CR13","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., 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":"2","key":"167_CR14","first-page":"9","volume":"61","author":"W-K Hon","year":"2014","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Space-efficient frameworks for top-k string retrieval. J. ACM. 61(2), 9 (2014)","journal-title":"J. ACM."},{"key":"167_CR15","doi-asserted-by":"publisher","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top- $$k$$ k string retrieval problems. In: Proceedings of the 50th FOCS, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"issue":"5","key":"167_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"167_CR17","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows\u2013Wheeler transform. J. ACM. 48(3), 407\u2013430 (2001)","journal-title":"J. ACM."},{"key":"167_CR18","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Navarro, G., Nielsen, J.S., Shah, R., Thankachan, S.V.: Top-k term-proximity in succinct space. In: Proceedings of the 25th ISAAC, pp. 169\u2013180 (2014)","DOI":"10.1007\/978-3-319-13075-0_14"},{"key":"167_CR19","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of the 13th SODA, pp. 657\u2013666 (2002)"},{"issue":"4","key":"167_CR20","doi-asserted-by":"publisher","first-page":"Art. No. 52","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), Art. No. 52 (2014)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"167_CR21","doi-asserted-by":"publisher","first-page":"Art. No. 2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), Art. No. 2 (2007)","journal-title":"ACM Comput. Surv."},{"key":"167_CR22","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top- $$k$$ k document retrieval in optimal time and linear space. In: Proceedings of the 23rd SODA, pp. 1066\u20131078 (2012)","DOI":"10.1137\/1.9781611973099.84"},{"key":"167_CR23","doi-asserted-by":"publisher","unstructured":"Navarro, G., Russo, L.: Fast fully-compressed suffix trees. In: Proceedings of the 24th DCC, pp. 283\u2013291 (2014)","DOI":"10.1109\/DCC.2014.40"},{"key":"167_CR24","doi-asserted-by":"crossref","unstructured":"Navarro, G., Thankachan, S.V.: Faster top- $$k$$ k document retrieval in optimal space. In: Proceedings of the 20th SPIRE, LNCS 8214, pp. 255\u2013262 (2013)","DOI":"10.1007\/978-3-319-02432-5_28"},{"key":"167_CR25","doi-asserted-by":"crossref","unstructured":"Navarro, G., Thankachan, S.V.: Top- $$k$$ k document retrieval in compact space and near-optimal time. In: Proceedings of the 24th ISAAC, LNCS 8283, pp. 394\u2013404 (2013)","DOI":"10.1007\/978-3-642-45030-3_37"},{"key":"167_CR26","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2014.05.005","volume":"542","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Thankachan, S.V.: New space\/time tradeoffs for top- $$k$$ k document retrieval on sequences. Theor. Comput. Sci. 542, 83\u201397 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"167_CR27","doi-asserted-by":"publisher","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Proceedings of the 13th SWAT, LNCS 7357, pp. 271\u2013282 (2012)","DOI":"10.1007\/978-3-642-31155-0_24"},{"key":"167_CR28","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proceedings of the 49th FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"issue":"4","key":"167_CR29","doi-asserted-by":"publisher","first-page":"Art. No. 43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Srinivasa, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), Art. No. 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"167_CR30","doi-asserted-by":"publisher","unstructured":"Schenkel, R., Broschart, A., Hwang, S.-W., Theobald, M., Weikum, G.: Efficient text proximity search. In: SPIRE, pp. 287\u2013299 (2007)","DOI":"10.1007\/978-3-540-75530-2_26"},{"key":"167_CR31","doi-asserted-by":"publisher","unstructured":"Shah, R., Sheng, C., Thankachan, S.V., Vitter, J.S.: Top-k document retrieval in external memory. In: Proceedings of the 21st ESA, LNCS 8125, pp. 803\u2013814 (2013)","DOI":"10.1007\/978-3-642-40450-4_68"},{"key":"167_CR32","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"167_CR33","doi-asserted-by":"publisher","unstructured":"Yan, H., Shi, S., Zhang, F., Suel, T., Wen, J.-R.: Efficient term proximity search with term-pair indexes. In: CIKM, pp. 1229\u20131238 (2010)","DOI":"10.1145\/1871437.1871593"},{"key":"167_CR34","doi-asserted-by":"publisher","unstructured":"Zhu, M., Shi, S., Li, M., Wen, J.-R.: Effective top-k computation in retrieving structured documents with term-proximity support. In: CIKM, pp. 771\u2013780 (2007)","DOI":"10.1145\/1321440.1321547"},{"key":"167_CR35","doi-asserted-by":"publisher","unstructured":"Zhu, M., Shi, S., Yu, N., Wen, J.-R.: Can phrase indexing help to process non-phrase queries? In: CIKM, pp. 679\u2013688 (2008)","DOI":"10.1145\/1458082.1458174"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0167-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0167-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0167-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0167-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T19:48:40Z","timestamp":1748980120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0167-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,27]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["167"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0167-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,5,27]]}}}