{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:33:12Z","timestamp":1725744792466},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","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-40273-9_22","type":"book-chapter","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T21:20:34Z","timestamp":1376083234000},"page":"351-362","source":"Crossref","is-referenced-by-count":8,"title":["Indexes for Document Retrieval with Relevance"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[]},{"given":"Manish","family":"Patil","sequence":"additional","affiliation":[]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_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":"22_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":"22_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":"22_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proc. 18th Symposium on Principles of Database Systems (PODS), pp. 346\u2013357 (1999)","DOI":"10.1145\/303976.304010"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-642-24583-1_38","volume-title":"String Processing and Information Retrieval","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Improved compressed indexes for full-text document retrieval. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 386\u2013397. Springer, Heidelberg (2011)"},{"issue":"2","key":"22_CR6","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":"22_CR7","doi-asserted-by":"crossref","unstructured":"Chien, Y.-F., Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Geometric burrows-wheeler transform: Compressed text indexing via sparse suffixes and range searching. Algorithmica (2013)","DOI":"10.1007\/s00453-013-9792-1"},{"issue":"40-42","key":"22_CR8","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.\u00a0411(40-42), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"22_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)"},{"issue":"4","key":"22_CR11","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\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"22_CR12","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)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-38905-4_12","volume-title":"Combinatorial Pattern Matching","author":"T. Gagie","year":"2013","unstructured":"Gagie, T., Karhu, K., Navarro, G., Puglisi, S.J., Sir\u00e9n, J.: Document listing on repetitive collections. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 107\u2013119. Springer, Heidelberg (2013)"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-16321-0_7","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2010","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 67\u201381. Springer, Heidelberg (2010)"},{"key":"22_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."},{"issue":"2","key":"22_CR16","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.\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"22_CR17","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.jda.2010.08.003","volume":"8","author":"W.-K. 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\u00a08(4), 402\u2013417 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"22_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":"22_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":"22_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":"22_CR21","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed top-k document retrieval. In: DCC (2013)"},{"key":"22_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":"22_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":"22_CR24","doi-asserted-by":"crossref","unstructured":"Culpepper, M.P.J.S., Scholer, F.: Efficient in-memory top-k document retrieval. In: SIGIR (2012)","DOI":"10.1145\/2348283.2348317"},{"key":"22_CR25","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":"22_CR26","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":"22_CR27","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":"22_CR28","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp. 657\u2013666 (2002)"},{"key":"22_CR29","unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. CoRR, abs\/1304.6023 (2013)"},{"key":"22_CR30","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":"22_CR31","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":"22_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-642-20662-7_17","volume-title":"Experimental Algorithms","author":"G. Navarro","year":"2011","unstructured":"Navarro, G., Puglisi, S.J., Valenzuela, D.: Practical compressed document retrieval. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 193\u2013205. Springer, Heidelberg (2011)"},{"key":"22_CR33","unstructured":"Navarro, G., Thankachan, S.V.: Faster top-k document retrieval in optimal space (submitted)"},{"key":"22_CR34","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":"22_CR35","unstructured":"Nekrich, Y., Patil, M., Shah, R., Thankachan, S.V., Vitter, J.S.: Top-k categorical range maxima queries (submitted)"},{"key":"22_CR36","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":"22_CR37","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":"22_CR38","unstructured":"Shah, R., Sheng, C., Thankachan, S.V., Vitter, J.S.: On optimal top-k string retrieval. CoRR, abs\/1207.2632 (2012)"},{"issue":"12","key":"22_CR39","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.\u00a0113(12), 440\u2013443 (2013)","journal-title":"Inf. Process. Lett."},{"key":"22_CR40","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":"22_CR41","doi-asserted-by":"crossref","unstructured":"Vitter, J.S.: Compressed data structures with relevance. In: CIKM, pp. 4\u20135 (2012)","DOI":"10.1145\/2396761.2396765"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T10:31:07Z","timestamp":1558002667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}