{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:41Z","timestamp":1759638881747},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_68","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"803-814","source":"Crossref","is-referenced-by-count":14,"title":["Top-k Document Retrieval in External Memory"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Shah","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Sheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"68_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-87744-8_4","volume-title":"Algorithms - ESA 2008","author":"P. Afshani","year":"2008","unstructured":"Afshani, P.: On dominance reporting in 3D. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 41\u201351. Springer, Heidelberg (2008)"},{"key":"68_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., Brodal, G.S., Zeh, N.: Ordered and unordered top-k range reporting in large data sets. In: SODA, pp. 390\u2013400 (2011)","DOI":"10.1137\/1.9781611973082.31"},{"issue":"9","key":"68_CR3","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"68_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: PODS, pp. 346\u2013357 (1999)","DOI":"10.1145\/303976.304010"},{"key":"68_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval, vol.\u00a018, pp. 3\u201313 (2013)","DOI":"10.1016\/j.jda.2012.07.005"},{"issue":"4","key":"68_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"68_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-10631-6_19","volume-title":"Algorithms and Computation","author":"G.S. Brodal","year":"2009","unstructured":"Brodal, G.S., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 173\u2013182. Springer, Heidelberg (2009)"},{"key":"68_CR8","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: STACS, pp. 290\u2013301 (2012)","DOI":"10.1007\/978-3-642-31155-0_26"},{"issue":"2","key":"68_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching: I. the reporting case. J. ACM\u00a037(2), 200\u2013212 (1990)","journal-title":"J. ACM"},{"key":"68_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-15781-3_17","volume-title":"Algorithms \u2013 ESA 2010","author":"J.S. Culpepper","year":"2010","unstructured":"Culpepper, J.S., Navarro, G., Puglisi, S.J., Turpin, A.: Top-k ranked document search in general text databases. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol.\u00a06347, pp. 194\u2013205. Springer, Heidelberg (2010)"},{"key":"68_CR11","doi-asserted-by":"crossref","unstructured":"Culpepper, J.S., Petri, M., Scholer, F.: Efficient in-memory top-k document retrieval. In: SIGIR (2012)","DOI":"10.1145\/2348283.2348317"},{"issue":"2","key":"68_CR12","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\u00a046(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"key":"68_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-29344-3_28","volume-title":"LATIN 2012: Theoretical Informatics","author":"J. Fischer","year":"2012","unstructured":"Fischer, J., Gagie, T., Kopelowitz, T., Lewenstein, M., M\u00e4kinen, V., Salmela, L., V\u00e4lim\u00e4ki, N.: Forbidden patterns. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 327\u2013337. Springer, Heidelberg (2012)"},{"issue":"3","key":"68_CR14","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"68_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2011.12.002","volume":"426","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.\u00a0426, 25\u201341 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"68_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-642-14165-2_51","volume-title":"Automata, Languages and Programming","author":"M. Greve","year":"2010","unstructured":"Greve, M., J\u00f8rgensen, A.G., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 605\u2013616. Springer, Heidelberg (2010)"},{"key":"68_CR17","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Patil, M., Shah, R., Thankachan, S.V., Vitter, J.S.: Indexes for document retrieval with relevance. In: Munro Festschrift, pp. 351\u2013362 (2013)","DOI":"10.1007\/978-3-642-40273-9_22"},{"key":"68_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-31265-6_14","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V.: Towards an optimal space-and-query-time index for top-k document retrieval. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 173\u2013184. Springer, Heidelberg (2012)"},{"key":"68_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-16321-0_6","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: String retrieval for multi-pattern queries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 55\u201366. Springer, Heidelberg (2010)"},{"key":"68_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-31265-6_15","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Document listing for queries with excluded pattern. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 185\u2013195. Springer, Heidelberg (2012)"},{"key":"68_CR21","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed top-k document retrieval. In: DCC (2013)"},{"key":"68_CR22","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: FOCS 2009, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"68_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-13509-5_24","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Compression, indexing, and retrieval for massive string data. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 260\u2013274. Springer, Heidelberg (2010)"},{"key":"68_CR24","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: SODA, pp. 401\u2013411 (2011)","DOI":"10.1137\/1.9781611973082.32"},{"key":"68_CR25","doi-asserted-by":"crossref","unstructured":"Konow, R., Navarro, G.: Faster compact top-k document retrieval. In: DCC (2013)","DOI":"10.1109\/DCC.2013.43"},{"key":"68_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-31265-6_16","volume-title":"Combinatorial Pattern Matching","author":"G. Kucherov","year":"2012","unstructured":"Kucherov, G., Nekrich, Y., Starikovskaya, T.: Cross-document pattern matching. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 196\u2013207. Springer, Heidelberg (2012)"},{"issue":"2","key":"68_CR27","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1109\/TCBB.2011.127","volume":"9","author":"M.O. K\u00fclekci","year":"2012","unstructured":"K\u00fclekci, M.O., Vitter, J.S., Xu, B.: Efficient maximal repeat finding using the burrows-wheeler transform and wavelet tree. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a09(2), 421\u2013429 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"68_CR28","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Pagh, R.: I\/o-efficient data structures for colored range and prefix reporting. In: SODA, pp. 583\u2013592 (2012)","DOI":"10.1137\/1.9781611973099.49"},{"key":"68_CR29","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., van Walderveen, F.: Near-optimal range reporting structures for categorical data. In: SODA, pp. 265\u2013276 (2013)","DOI":"10.1137\/1.9781611973105.20"},{"key":"68_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-68530-8_6","volume-title":"Algorithms - ESA \u201998","author":"Y. Matias","year":"1998","unstructured":"Matias, Y., Muthukrishnan, S.M., \u015eahinalp, S.C., Ziv, J.: Augmenting suffix trees, with applications. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 67\u201378. Springer, Heidelberg (1998)"},{"key":"68_CR31","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp. 657\u2013666 (2002)"},{"key":"68_CR32","unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. CoRR, abs\/1304.6023 (2013)"},{"key":"68_CR33","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top- k document retrieval in optimal time and linear space. In: SODA, pp. 1066\u20131077 (2012)","DOI":"10.1137\/1.9781611973099.84"},{"key":"68_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-16321-0_33","volume-title":"String Processing and Information Retrieval","author":"G. Navarro","year":"2010","unstructured":"Navarro, G., Puglisi, S.J.: Dual-sorted inverted lists. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 309\u2013321. Springer, Heidelberg (2010)"},{"key":"68_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-30850-5_27","volume-title":"Experimental Algorithms","author":"G. Navarro","year":"2012","unstructured":"Navarro, G., Valenzuela, D.: Space-efficient top-k document retrieval. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 307\u2013319. Springer, Heidelberg (2012)"},{"key":"68_CR36","doi-asserted-by":"crossref","unstructured":"Nekrich, Y.: Space-efficient range reporting for categorical data. In: PODS, pp. 113\u2013120 (2012)","DOI":"10.1145\/2213556.2213575"},{"key":"68_CR37","doi-asserted-by":"crossref","unstructured":"Patil, M., Thankachan, S.V., Shah, R., Hon, W.-K., Vitter, J.S., Chandrasekaran, S.: Inverted indexes for phrases and strings. In: SIGIR, pp. 555\u2013564 (2011)","DOI":"10.1145\/2009916.2009992"},{"issue":"1","key":"68_CR38","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"68_CR39","doi-asserted-by":"crossref","unstructured":"Sheng, C., Tao, Y.: Dynamic top-k range reporting in external memory. In: PODS, pp. 121\u2013130 (2012)","DOI":"10.1145\/2213556.2213576"},{"key":"68_CR40","unstructured":"Tao, Y.: Lecture 1: External memory model and sorting"},{"key":"68_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-13509-5_8","volume-title":"Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2010","unstructured":"V\u00e4lim\u00e4ki, N., Ladra, S., M\u00e4kinen, V.: Approximate all-pairs suffix\/Prefix overlaps. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 76\u201387. Springer, Heidelberg (2010)"},{"key":"68_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73437-6_22","volume-title":"Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2007","unstructured":"V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Space-efficient algorithms for document retrieval. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 205\u2013215. Springer, Heidelberg (2007)"},{"key":"68_CR43","doi-asserted-by":"crossref","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv.\u00a038(2) (July 2006)","DOI":"10.1145\/1132956.1132959"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:51:26Z","timestamp":1558317086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}