{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:04Z","timestamp":1759638064883,"version":"3.40.5"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_14","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"169-180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Top-$$k$$ Term-Proximity in Succinct Space"],"prefix":"10.1007","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":[[2014,11,8]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval, 2nd edn. Addison-Wesley (2011)","key":"14_CR1","DOI":"10.1145\/2009916.2010172"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"14_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. Discr. Alg. 18, 3\u201313 (2013)","journal-title":"J. Discr. Alg."},{"doi-asserted-by":"crossref","unstructured":"Benson, G., Waterman, M.: A fast method for fast database search for all $$k$$-nucleotide repeats. Nucleic Acids Research 22(22) (1994)","key":"14_CR4","DOI":"10.1093\/nar\/22.22.4828"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-14556-8_22","volume-title":"Focused Retrieval and Evaluation","author":"A Broschart","year":"2010","unstructured":"Broschart, A., Schenkel, R.: Index tuning for efficient proximity-enhanced query processing. In: Geva, S., Kamps, J., Trotman, A. (eds.) INEX 2009. LNCS, vol. 6203, pp. 213\u2013217. Springer, Heidelberg (2010)"},{"unstructured":"B\u00fcttcher, S., Clarke, C.L.A., Cormack, G.: Information Retrieval: Implementing and Evaluating Search Engines. MIT Press (2010)","key":"14_CR6"},{"issue":"2","key":"14_CR7","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"},{"issue":"4","key":"14_CR8","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg. 3(2), art. 20 (2007)","key":"14_CR9","DOI":"10.1145\/1240233.1240243"},{"key":"14_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. Comp. Sci. 426\u2013427, 25\u201341 (2012)","journal-title":"Theor. Comp. Sci."},{"issue":"2","key":"14_CR11","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press (1997)","key":"14_CR12","DOI":"10.1017\/CBO9780511574931"},{"key":"14_CR13","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. Discr. Alg. 17, 109\u2013114 (2012)","journal-title":"J. Discr. Alg."},{"doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed top-k document retrieval. In: Proc. 23rd DCC, pp. 341\u2013350 (2013)","key":"14_CR14","DOI":"10.1109\/DCC.2013.42"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2590774","volume":"61","author":"W-K Hon","year":"2014","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Scott Vitter, J.: Space-efficient frameworks for top- k string retrieval. J. ACM 61(2), 9 (2014)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top-$$k$$ string retrieval problems. In: Proc. 50th FOCS, pp. 713\u2013722 (2009)","key":"14_CR16","DOI":"10.1109\/FOCS.2009.19"},{"issue":"5","key":"14_CR17","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. Comp. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comp."},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-319-08404-6_30","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"JI Munro","year":"2014","unstructured":"Munro, J.I., Navarro, G., Shah, R., Thankachan, S.V.: Ranked document selection. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 344\u2013356. Springer, Heidelberg (2014)"},{"unstructured":"Muthukrishnan, S.; Efficient algorithms for document retrieval problems. In: Proc. 13th SODA, pp. 657\u2013666 (2002)","key":"14_CR19"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. ACM Comp. Surv. 46(4), art. 52 (2014)","key":"14_CR20","DOI":"10.1145\/2535933"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv. 39(1), art. 2 (2007)","key":"14_CR21","DOI":"10.1145\/1216370.1216372"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top-$$k$$ document retrieval in optimal time and linear space. In: Proc. 23rd SODA, pp. 1066\u20131078 (2012)","key":"14_CR22","DOI":"10.1137\/1.9781611973099.84"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., Russo, L.: Fast fully-compressed suffix trees. In: Proc. 24th DCC, pp. 283\u2013291 (2014)","key":"14_CR23","DOI":"10.1109\/DCC.2014.40"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-319-02432-5_28","volume-title":"String Processing and Information Retrieval","author":"G Navarro","year":"2013","unstructured":"Navarro, G., Thankachan, S.V.: Faster top-k document retrieval in optimal space. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 255\u2013262. Springer, Heidelberg (2013)"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-45030-3_37","volume-title":"Algorithms and Computation","author":"G Navarro","year":"2013","unstructured":"Navarro, G., Thankachan, S.V.: Top-k document retrieval in compact space and near-optimal time. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 394\u2013404. Springer, Heidelberg (2013)"},{"key":"14_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 document retrieval on sequences. Theor. Comput. Sci. 542, 83\u201397 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-31155-0_24","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"Y Nekrich","year":"2012","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 271\u2013282. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proc. 49th FOCS, pp. 305\u2013313 (2008)","key":"14_CR28","DOI":"10.1109\/FOCS.2008.83"},{"key":"14_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-540-75530-2_26","volume-title":"String Processing and Information Retrieval","author":"R Schenkel","year":"2007","unstructured":"Schenkel, R., Broschart, A., Hwang, S., Theobald, M., Weikum, G.: Efficient text proximity search. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 287\u2013299. Springer, Heidelberg (2007)"},{"key":"14_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/978-3-642-40450-4_68","volume-title":"Algorithms \u2013 ESA 2013","author":"R Shah","year":"2013","unstructured":"Shah, R., Sheng, C., Thankachan, S.V., Vitter, J.S.: Top-k document retrieval in external memory. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 803\u2013814. Springer, Heidelberg (2013)"},{"doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","key":"14_CR31","DOI":"10.1109\/SWAT.1973.13"},{"doi-asserted-by":"crossref","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)","key":"14_CR32","DOI":"10.1145\/1871437.1871593"},{"doi-asserted-by":"crossref","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)","key":"14_CR33","DOI":"10.1145\/1321440.1321547"},{"doi-asserted-by":"crossref","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)","key":"14_CR34","DOI":"10.1145\/1458082.1458174"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:11:19Z","timestamp":1747159879000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}