{"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":1781259526824,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540755197","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_34","type":"book-chapter","created":{"date-parts":[[2007,9,13]],"date-time":"2007-09-13T23:46:33Z","timestamp":1189727193000},"page":"371-382","source":"Crossref","is-referenced-by-count":19,"title":["On the Size of Succinct Indices"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Golynski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ankur","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satti Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci.\u00a065, 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in Constant Time and Almost-Minimum Space. SIAM J. Computing\u00a028, 1627\u20131640 (1999)","journal-title":"SIAM J. Computing"},{"key":"34_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/11764298_12","volume-title":"Experimental Algorithms","author":"O. Delpratt","year":"2006","unstructured":"Delpratt, O., Rahman, N., Raman, R.: Engineering the LOUDS succinct tree representation. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 134\u2013145. Springer, Heidelberg (2006)"},{"key":"34_CR4","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., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci.\u00a0379, 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","volume":"368","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci.\u00a0368, 231\u2013246 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"34_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/11786986_33","volume-title":"Automata, Languages and Programming","author":"A. Golynski","year":"2006","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 370\u2013381. Springer, Heidelberg (2006)"},{"key":"34_CR7","first-page":"841","volume-title":"Proc. 14th ACM-SIAM SODA","author":"R. Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th ACM-SIAM SODA, pp. 841\u2013850. ACM Press, New York (2003)"},{"key":"34_CR8","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: When indexing equals compression: experiments with compressing suffix arrays and applications. In: SODA 2004, pp. 636\u2013645"},{"key":"34_CR9","first-page":"549","volume-title":"Proc. 30th IEEE Symp. FOCS","author":"G. Jacobson","year":"1989","unstructured":"Jacobson, G.: Space efficient static trees and graphs. In: Proc. 30th IEEE Symp. FOCS, pp. 549\u2013554. IEEE Computer Society Press, Los Alamitos (1989)"},{"key":"34_CR10","first-page":"11","volume-title":"Proceedings of the ACM-SIAM SODA","author":"P.B. Miltersen","year":"2005","unstructured":"Miltersen, P.B.: Lower bounds on the size of selection and rank indexes. In: Proceedings of the ACM-SIAM SODA, pp. 11\u201312. ACM Press, New York (2005)"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput.\u00a031, 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"34_CR12","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":"34_CR13","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":"34_CR14","first-page":"232","volume-title":"Proc. 38th ACM STOC","author":"M. Patrascu","year":"2006","unstructured":"Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th ACM STOC, pp. 232\u2013240. ACM Press, New York (2006)"},{"key":"34_CR15","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries, with applications to representing k-ary trees and multisets. In: ACM-SIAM SODA 2003, pp. 233\u2013242"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:22:52Z","timestamp":1619504572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_34","relation":{},"subject":[]}}