{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:35:09Z","timestamp":1725744909498},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_47","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"553-564","source":"Crossref","is-referenced-by-count":8,"title":["Encodings\u00a0for\u00a0Range\u00a0Selection\u00a0and\u00a0Top-k\u00a0Queries"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satti Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with o(1) accesses. In: Proc. SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"issue":"1","key":"47_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M. Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comp. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theor. Comp. Sci."},{"issue":"2","key":"47_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comp.\u00a022(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comp."},{"key":"47_CR4","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)"},{"issue":"24","key":"47_CR5","doi-asserted-by":"publisher","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"G. Brodal","year":"2011","unstructured":"Brodal, G., Gfeller, B., J\u00f8rgensen, A., Sanders, P.: Towards optimal range medians. Theor. Comp. Sci.\u00a0412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comp. Sci."},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T., Wilkinson, B.: Adaptive and approximate orthogonal range counting. In: Proc. SODA, pp. 241\u2013251 (2013)","DOI":"10.1137\/1.9781611973105.18"},{"key":"47_CR7","unstructured":"Clark, D.: Compact Pat Trees. Ph.D. thesis, Univ. of Waterloo, Canada (1996)"},{"issue":"2","key":"47_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comp.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comp."},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Puglisi, S.: New algorithms on wavelet trees and applications to information retrieval. Theor. Comp. Sci., 426\u2013427, 25\u201341 (2012)","DOI":"10.1016\/j.tcs.2011.12.002"},{"key":"47_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S., Turpin, A.: Range quantile queries: another virtue of wavelet trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, I., Rao, S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proc. SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"issue":"2","key":"47_CR12","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. Comp.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comp."},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"Hsu, P., Ottaviano, G.: Space-efficient data structures for top-k completion. In: Proc. WWW, pp. 583\u2013594 (2013)","DOI":"10.1145\/2488388.2488440"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A., Larsen, K.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: Proc. SODA, pp. 805\u2013813 (2011)","DOI":"10.1137\/1.9781611973082.63"},{"key":"47_CR15","doi-asserted-by":"crossref","unstructured":"Li, G., Ji, S., Li, C., Feng, J.: Efficient type-ahead search on relational data: a tastier approach. In: Proc. SIGMOD, pp. 695\u2013706. ACM (2009)","DOI":"10.1145\/1559845.1559918"},{"key":"47_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"I. Munro","year":"1996","unstructured":"Munro, I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"47_CR17","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proc. FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"issue":"4","key":"47_CR18","first-page":"1","volume":"2","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Alg.\u00a02(4), 43:1\u201343:25 (2007)","journal-title":"ACM Trans. Alg."},{"key":"47_CR19","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: Proc. SODA, pp. 225\u2013232 (2002)"},{"key":"47_CR20","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"4","key":"47_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Comm. ACM\u00a023(4), 229\u2013239 (1980)","journal-title":"Comm. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:55:20Z","timestamp":1558011320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}