{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:18:46Z","timestamp":1781259526557,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540699002","type":"print"},{"value":"9783540699033","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-69903-3_15","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"148-159","source":"Crossref","is-referenced-by-count":19,"title":["On the Redundancy of Succinct Data Structures"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Golynski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proc. 18th SODA, pp. 680\u2013689 (2007)"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica\u00a043, 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Delpratt, O., Raman, R., Rahman, N.: Engineering succinct DOM. In: Proc. 11th EDBT, pp. 49\u201360 (2008)","DOI":"10.1145\/1353343.1353354"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. 46th FOCS, pp. 184\u2013196 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms 3, Article 20 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"15_CR6","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, 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"15_CR7","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, 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR8","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":"15_CR9","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms\u00a02, 510\u2013534 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"15_CR10","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. Theor. Comput. Sci.\u00a0387, 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR11","unstructured":"Golynski, A.: Upper and Lower Bounds for Text Indexing Data Structures. PhD thesis, University of Waterloo (2007)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-75520-3_34","volume-title":"Algorithms \u2013 ESA 2007","author":"A. Golynski","year":"2007","unstructured":"Golynski, A., Grossi, R., Gupta, A., Raman, R., Rao, S.S.: On the size of succinct indices. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 371\u2013382. Springer, Heidelberg (2007)"},{"key":"15_CR13","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850 (2003)"},{"key":"15_CR14","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, 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space efficient static trees and graphs. In: Proc. 30th FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"15_CR16","unstructured":"Miltersen, P.B.: Lower bounds on the size of selection and rank indexes. In: Proc. 16th SODA, pp. 11\u201312 (2005)"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"15_CR18","first-page":"59","volume-title":"Proc. 9th ALENEX","author":"D. Okanohara","year":"2007","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. 9th ALENEX, pp. 59\u201370. SIAM, Philadelphia (2007)"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Computing\u00a031, 353\u2013363 (2001)","journal-title":"SIAM J. Computing"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"15_CR21","first-page":"26","volume":"4","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries, with applications to representing k-ary trees, prefix sums and multisets. ACM Trans. Algorithms\u00a04, 26 (2007), Article 43","journal-title":"ACM Trans. Algorithms"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy-compressed bounds. In: Proc. 17th SODA, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69903-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:09:10Z","timestamp":1738325350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-69903-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540699002","9783540699033"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69903-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}