{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:58Z","timestamp":1781078218492,"version":"3.54.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>\n            We consider the\n            <jats:italic>indexable dictionary<\/jats:italic>\n            problem, which consists of storing a set\n            <jats:italic>S<\/jats:italic>\n            \u2286 {0,\u2026,\n            <jats:italic>m<\/jats:italic>\n            \u2212 1} for some integer\n            <jats:italic>m<\/jats:italic>\n            while supporting the operations of rank(\n            <jats:italic>x<\/jats:italic>\n            ), which returns the number of elements in\n            <jats:italic>S<\/jats:italic>\n            that are less than\n            <jats:italic>x<\/jats:italic>\n            if\n            <jats:italic>x<\/jats:italic>\n            \u2208\n            <jats:italic>S<\/jats:italic>\n            , and \u22121 otherwise; and select(\n            <jats:italic>i<\/jats:italic>\n            ), which returns the\n            <jats:italic>i<\/jats:italic>\n            th smallest element in\n            <jats:italic>S<\/jats:italic>\n            . We give a data structure that supports both operations in\n            <jats:italic>O<\/jats:italic>\n            (1) time on the RAM model and requires B(\n            <jats:italic>n, m<\/jats:italic>\n            ) +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>O<\/jats:italic>\n            (lg lg\n            <jats:italic>m<\/jats:italic>\n            ) bits to store a set of size\n            <jats:italic>n<\/jats:italic>\n            , where B(\n            <jats:italic>n, m<\/jats:italic>\n            ) = \u230alg (\n            <jats:italic>m<\/jats:italic>\n            \/\n            <jats:italic>n<\/jats:italic>\n            )\u230b is the minimum number of bits required to store any\n            <jats:italic>n<\/jats:italic>\n            -element subset from a universe of size\n            <jats:italic>m<\/jats:italic>\n            . Previous dictionaries taking this space only supported (yes\/no) membership queries in\n            <jats:italic>O<\/jats:italic>\n            (1) time. In the cell probe model we can remove the\n            <jats:italic>O<\/jats:italic>\n            (lg lg\n            <jats:italic>m<\/jats:italic>\n            ) additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001].\n          <\/jats:p>\n          <jats:p>We present extensions and applications of our indexable dictionary data structure, including:<\/jats:p>\n          <jats:p>\n            \u2014an information-theoretically optimal representation of a\n            <jats:italic>k<\/jats:italic>\n            -ary cardinal tree that supports standard operations in constant time;\n          <\/jats:p>\n          <jats:p>\n            \u2014a representation of a multiset of size\n            <jats:italic>n<\/jats:italic>\n            from {0,\u2026,\n            <jats:italic>m<\/jats:italic>\n            \u2212 1} in B(\n            <jats:italic>n, m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits that supports (appropriate generalizations of) rank and select operations in constant time; and +\n            <jats:italic>O<\/jats:italic>\n            (lg lg\n            <jats:italic>m<\/jats:italic>\n            )\n          <\/jats:p>\n          <jats:p>\n            \u2014a representation of a sequence of\n            <jats:italic>n<\/jats:italic>\n            nonnegative integers summing up to\n            <jats:italic>m<\/jats:italic>\n            in B(\n            <jats:italic>n, m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits that supports prefix sum queries in constant time.\n          <\/jats:p>","DOI":"10.1145\/1290672.1290680","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":310,"title":["Succinct indexable dictionaries with applications to encoding\n            <i>k<\/i>\n            -ary trees, prefix sums and multisets"],"prefix":"10.1145","volume":"3","author":[{"given":"Rajeev","family":"Raman","sequence":"first","affiliation":[{"name":"University of Leicester, Leicester, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1983. Data Structures and Algorithms. Addison-Wesley.   Aho A. V. Hopcroft J. E. and Ullman J. D. 1983. Data Structures and Algorithms. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80015-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1146-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230305"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 4th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"955","author":"Fich F. E.","unstructured":"Fich , F. E. and Miltersen , P. B . 1995. Tables should be sorted (on random access machines) . In Proceedings of the 4th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science , vol. 955 . Springer, 482--493. Fich, F. E. and Miltersen, P. B. 1995. Tables should be sorted (on random access machines). In Proceedings of the 4th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 955. Springer, 482--493."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198516"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109599"},{"key":"e_1_2_1_18_1","unstructured":"Graham R. L. Knuth D. E. and Patashnik O. 1994. Concrete Mathematics. Addison-Wesley.   Graham R. L. Knuth D. E. and Patashnik O. 1994. Concrete Mathematics. Addison-Wesley."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). Society for Industrial and Applied Mathematics","author":"Grossi R.","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2003. High-Order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). Society for Industrial and Applied Mathematics , Philadelphia, PA, 841--850. Grossi, R., Gupta, A., and Vitter, J. S. 2003. High-Order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 841--850."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science","author":"Hagerup T.","unstructured":"Hagerup , T. 1998. Sorting and searching on the word RAM . In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science . Lecture Notes in Computer Science , vol. 1373 . Springer , 366--398. Hagerup, T. 1998. Sorting and searching on the word RAM. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1373. Springer, 366--398."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2010","author":"Hagerup T.","unstructured":"Hagerup , T. and Tholey , T . 2001. Efficient minimal perfect hashing in nearly minimal space . In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science , vol. 2010 . Springer, 317--326. Hagerup, T. and Tholey, T. 2001. Efficient minimal perfect hashing in nearly minimal space. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2010. Springer, 317--326."},{"key":"e_1_2_1_24_1","volume-title":"-K","author":"Jansson J.","year":"2007","unstructured":"Jansson , J. , Sadakane , K. , and Sung , W . -K . 2007 . Ultra-Succinct representation of ordered trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. Jansson, J., Sadakane, K., and Sung, W.-K. 2007. Ultra-Succinct representation of ordered trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Munro J. I.","unstructured":"Munro , J. I. 1996. Tables . In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science , vol. 1180 . Springer , 37--42. Munro, J. I. 1996. Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1180. Springer, 37--42."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Symposium on Logic and Algorithmic, 331--340","author":"Paul W. J.","unstructured":"Paul , W. J. and Simon , J . 1980. Decision trees and random access machines . In Proceedings of the International Symposium on Logic and Algorithmic, 331--340 . Paul, W. J. and Simon, J. 1980. Decision trees and random access machines. In Proceedings of the International Symposium on Logic and Algorithmic, 331--340."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 233--242","author":"Raman R.","unstructured":"Raman , R. , Raman , V. , and Rao , S. S . 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 233--242 . Raman, R., Raman, V., and Rao, S. S. 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 233--242."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 10th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","volume":"1741","author":"Raman V.","unstructured":"Raman , V. and Rao , S. S . 1999. Static dictionaries supporting rank . In Proceedings of the 10th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science , vol. 1741 . Springer, 18--26. Raman, V. and Rao, S. S. 1999. Static dictionaries supporting rank. In Proceedings of the 10th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 1741. Springer, 18--26."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290680","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:24Z","timestamp":1750258344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290680"],"URL":"https:\/\/doi.org\/10.1145\/1290672.1290680","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}