{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:56Z","timestamp":1781078216329,"version":"3.54.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,16]],"date-time":"2013-03-16T00:00:00Z","timestamp":1363392000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00453-013-9767-2","type":"journal-article","created":{"date-parts":[[2013,3,15]],"date-time":"2013-03-15T18:10:58Z","timestamp":1363371058000},"page":"906-924","source":"Crossref","is-referenced-by-count":15,"title":["Optimal Indexes for Sparse Bit Vectors"],"prefix":"10.1007","volume":"69","author":[{"given":"Alexander","family":"Golynski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessio","family":"Orlandi","sequence":"additional","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","published-online":{"date-parts":[[2013,3,16]]},"reference":[{"issue":"4","key":"9767_CR1","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. ACM Trans. Algorithms 7(4), 52 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"9767_CR2","unstructured":"Clark, D.: Compact Pat trees. Ph.D. thesis, University of Waterloo (1997)"},{"key":"9767_CR3","series-title":"LNCS","first-page":"134","volume-title":"Proc. 5th WEA","author":"O. Delpratt","year":"2006","unstructured":"Delpratt, O., Rahman, N., Raman, R.: Engineering the LOUDS succinct tree representation. In: Proc. 5th WEA. LNCS, vol. 4007, pp. 134\u2013145 (2006)"},{"issue":"2","key":"9767_CR4","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P. Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"9767_CR5","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. Journal of the ACM 57(1) (2009)","DOI":"10.1145\/1613676.1613680"},{"issue":"4","key":"9767_CR6","doi-asserted-by":"crossref","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 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"9767_CR7","doi-asserted-by":"crossref","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. 372, 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9767_CR8","doi-asserted-by":"crossref","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. 379, 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9767_CR9","doi-asserted-by":"crossref","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 Trans. Algorithms 2(4), 510\u2013534 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"9767_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. 387, 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9767_CR11","series-title":"LNCS","first-page":"371","volume-title":"Proc. 15th ESA","author":"A. Golynski","year":"2007","unstructured":"Golynski, A., Grossi, R., Gupta, A., Raman, R., Rao, S.S.: On the size of succinct indices. In: Proc. 15th ESA. LNCS, vol.\u00a04698, pp.\u00a0371\u2013382 (2007)"},{"key":"9767_CR12","series-title":"LNCS","first-page":"294","volume-title":"CPM 2006","author":"R. Gonz\u00e1lez","year":"2006","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Statistical encoding of succinct data structures. In: CPM 2006. LNCS, vol. 4009, pp.\u00a0294\u2013305 (2006)"},{"key":"9767_CR13","first-page":"841","volume-title":"Proc. 14th SODA","author":"R. Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp.\u00a0841\u2013850 (2003)"},{"key":"9767_CR14","doi-asserted-by":"crossref","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. 35, 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9767_CR15","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.tcs.2007.07.042","volume":"387","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. Theor. Comput. Sci. 387(3), 313\u2013331 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9767_CR16","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"M.E. Hellman","year":"1980","unstructured":"Hellman, M.E.: A cryptanalytic time-memory tradeoff. IEEE Trans. Inf. Theory 26, 401\u2013406 (1980)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9767_CR17","first-page":"549","volume-title":"Proc. 30th FOCS","author":"G. Jacobson","year":"1989","unstructured":"Jacobson, G.: Space efficient static trees and graphs. In: Proc. 30th FOCS, pp.\u00a0549\u2013554 (1989)"},{"key":"9767_CR18","first-page":"11","volume-title":"Proc. 16th SODA","author":"P.B. Miltersen","year":"2005","unstructured":"Miltersen, P.B.: Lower bounds on the size of selection and rank indexes. In: Proc. 16th SODA, pp.\u00a011\u201312 (2005)"},{"key":"9767_CR19","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.\u00a059\u201370 (2007)"},{"key":"9767_CR20","first-page":"3","volume-title":"Proc. 4th International Conference on Web Information Systems Engineering (WISE 2003)","author":"M.P. Papazouglou","year":"2003","unstructured":"Papazouglou, M.P.: Service-oriented computing: concepts, characteristics and directions. In: Proc. 4th International Conference on Web Information Systems Engineering (WISE 2003), pp.\u00a03\u201312 (2003)"},{"key":"9767_CR21","first-page":"305","volume-title":"Proc. 49th FOCS","author":"M. P\u01cetra\u015fcu","year":"2008","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proc. 49th FOCS, pp. 305\u2013313 (2008)"},{"key":"9767_CR22","first-page":"232","volume-title":"Proc. 38th STOC","author":"M. P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp.\u00a0232\u2013240 (2006)"},{"key":"9767_CR23","first-page":"117","volume-title":"Proc. 21st SODA","author":"M. P\u01cetra\u015fcu","year":"2010","unstructured":"P\u01cetra\u015fcu, M., Viola, E.: Cell-probe lower bounds for succinct partial sums. In: Proc. 21st SODA, pp.\u00a0117\u2013122 (2010)"},{"key":"9767_CR24","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1007\/978-0-387-30162-4_332","volume-title":"Encyclopaedia of Algorithms","author":"N. Rahman","year":"2008","unstructured":"Rahman, N., Raman, R.: Rank and select operations on binary strings. In: Kao, M.-Y. (ed.) Encyclopaedia of Algorithms, pp.\u00a0748\u2013751. Springer, Berlin (2008)"},{"issue":"4","key":"9767_CR25","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","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 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9767_CR26","first-page":"1230","volume-title":"Proc. 17th SODA","author":"K. Sadakane","year":"2006","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy-compressed bounds. In: Proc. 17th SODA, pp.\u00a01230\u20131239 (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9767-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9767-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9767-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:11Z","timestamp":1559123111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9767-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,16]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9767"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9767-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,16]]}}}