{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T11:25:28Z","timestamp":1777029928888,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642141645","type":"print"},{"value":"9783642141652","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_57","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"678-689","source":"Crossref","is-referenced-by-count":15,"title":["Optimal Trade-Offs for Succinct String Indexes"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[]},{"given":"Alessio","family":"Orlandi","sequence":"additional","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"#cr-split#-57_CR1.1","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proc. SODA 2007, pp. 680???689 (2007);"},{"key":"#cr-split#-57_CR1.2","unstructured":"Also, full version available in Internet"},{"key":"57_CR2","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 2009, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"57_CR3","series-title":"Series in Telecommunications and Signal Processing)","volume-title":"Elements of Information Theory","author":"T.M. Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Series in Telecommunications and Signal Processing). Wiley-Interscience, Hoboken (2006)"},{"issue":"1","key":"57_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0196-6774(03)00043-9","volume":"48","author":"E.D. Demaine","year":"2003","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A.: A linear lower bound on index size for text retrieval. J. Algorithms\u00a048(1), 2\u201315 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"57_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci.\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"57_CR6","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.tcs.2007.02.047","volume":"379","author":"A. G\u00e1l","year":"2007","unstructured":"G\u00e1l, A., Bro Miltersen, P.: The cell probe complexity of succinct data structures. Theor. Comput. Sci.\u00a0379, 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"57_CR7","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. TCS\u00a0387, 348\u2013359 (2007)","journal-title":"TCS"},{"key":"57_CR8","unstructured":"Golynski, A.: Upper and Lower Bounds for Text Indexing Data Structures. PhD Thesis, U. Waterloo (2007)"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Golynski, A.: Cell probe lower bounds for succinct data structures. In: Proc. SODA 2009, pp. 625\u2013632 (2009)","DOI":"10.1137\/1.9781611973068.69"},{"key":"57_CR10","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proc. SODA 2006, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"57_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/11780441_27","volume-title":"Combinatorial Pattern Matching","author":"R. Gonz\u00e1lez","year":"2006","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Statistical encoding of succinct data structures. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 294\u2013305. Springer, Heidelberg (2006)"},{"key":"57_CR12","unstructured":"Grossi, R., Orlandi, A., Raman, R., Rao, S.S.: More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In: Proc. STACS 2009, pp. 517\u2013528 (2009)"},{"key":"57_CR13","unstructured":"Miltersen, P.B.: Lower bounds on the size of selection and rank indexes. In: Proc. SODA 2005, pp. 11\u201312 (2005)"},{"key":"57_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-45061-0_29","volume-title":"Automata, Languages and Programming","author":"J.I. Munro","year":"2003","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 345\u2013356. Springer, Heidelberg (2003)"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proc. FOCS 2008, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries, with applications to representing k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a04 (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proc. SODA 2006, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"},{"issue":"2","key":"57_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space Theta(N). IPL\u00a017(2), 81\u201384 (1983)","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:23Z","timestamp":1606186103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}