{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:48:49Z","timestamp":1793850529495,"version":"4.6.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Academy of Finland","award":["250345 (Co-ECGR)"],"award-info":[{"award-number":["250345 (Co-ECGR)"]}]},{"name":"Fondecyt","award":["1-110066"],"award-info":[{"award-number":["1-110066"]}]},{"name":"French ANR-2010-COSI-004 MAPPI Project"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>\n            Sequence representations supporting the queries\n            <jats:italic>access<\/jats:italic>\n            ,\n            <jats:italic>select<\/jats:italic>\n            , and\n            <jats:italic>rank<\/jats:italic>\n            are at the core of many data structures. There is a considerable gap between the various upper bounds and the few lower bounds known for such representations, and how they relate to the space used. In this article, we prove a strong lower bound for\n            <jats:italic>rank<\/jats:italic>\n            , which holds for rather permissive assumptions on the space used, and give matching upper bounds that require only a compressed representation of the sequence. Within this compressed space, the operations\n            <jats:italic>access<\/jats:italic>\n            and\n            <jats:italic>select<\/jats:italic>\n            can be solved in constant or almost-constant time, which is optimal for large alphabets. Our new upper bounds dominate all of the previous work in the time\/space map.\n          <\/jats:p>","DOI":"10.1145\/2629339","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Optimal Lower and Upper Bounds for Representing Sequences"],"prefix":"10.1145","volume":"11","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology (HIIT) and University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Beauchef, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE). 417--428","author":"Arroyuelo D.","unstructured":"D. Arroyuelo , F. Claude , S. Maneth , V. M\u00e4kinen , G. Navarro , K. Nguy\u00ean , J. Sir\u00e9n , and N. V\u00e4lim\u00e4ki . 2010a. Fast in-memory xpath search over compressed text and tree indexes . In Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE). 417--428 . D. Arroyuelo, F. Claude, S. Maneth, V. M\u00e4kinen, G. Navarro, K. Nguy\u00ean, J. Sir\u00e9n, and N. V\u00e4lim\u00e4ki. 2010a. Fast in-memory xpath search over compressed text and tree indexes. In Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE). 417--428."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348320"},{"key":"e_1_2_1_3_1","volume-title":"String Processing and Information Retrieval. Lecture Notes in Computer Science","volume":"6393","author":"Arroyuelo D.","unstructured":"D. Arroyuelo , S. Gonz\u00e1lez , and M. Oyarz\u00fan . 2010b. Compressed self-indices supporting conjunctive queries on document collections . In String Processing and Information Retrieval. Lecture Notes in Computer Science , Vol. 6393 . Springer, 43--54. D. Arroyuelo, S. Gonz\u00e1lez, and M. Oyarz\u00fan. 2010b. Compressed self-indices supporting conjunctive queries on document collections. In String Processing and Information Retrieval. Lecture Notes in Computer Science, Vol. 6393. Springer, 43--54."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9726-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000820"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). 111--122","author":"Barbay J.","unstructured":"J. Barbay and G. Navarro . 2009. Compressed representations of permutations, and applications . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). 111--122 . J. Barbay and G. Navarro. 2009. Compressed representations of permutations, and applications. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). 111--122."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794","author":"Belazzougui D.","unstructured":"D. Belazzougui , P. Boldi , R. Pagh , and S. Vigna . 2009. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses . In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794 . D. Belazzougui, P. Boldi, R. Pagh, and S. Vigna. 2009. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794."},{"key":"e_1_2_1_8_1","volume-title":"Lecture Notes in Computer Science","volume":"6942","author":"Belazzougui D.","unstructured":"D. Belazzougui and G. Navarro . 2011. Alphabet-independent compressed text indexing. In Algorithms\u2014ESA 2011 . Lecture Notes in Computer Science , Vol. 6942 . Springer, 748--759. D. Belazzougui and G. Navarro. 2011. Alphabet-independent compressed text indexing. In Algorithms\u2014ESA 2011. Lecture Notes in Computer Science, Vol. 6942. Springer, 748--759."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-012-9184-1"},{"key":"e_1_2_1_12_1","volume-title":"Algorithms and Applications. Lecture Notes in Computer Science","volume":"6060","author":"Claude F.","unstructured":"F. Claude and G. Navarro . 2010. Extended compact Web graph representations . In Algorithms and Applications. Lecture Notes in Computer Science , Vol. 6060 . Springer, 77--91. F. Claude and G. Navarro. 2010. Extended compact Web graph representations. In Algorithms and Applications. Lecture Notes in Computer Science, Vol. 6060. Springer, 77--91."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.04.008"},{"key":"e_1_2_1_18_1","volume-title":"String Processing and Information Retrieval. Lecture Notes in Computer Science","volume":"6393","author":"Gagie T.","unstructured":"T. Gagie , G. Navarro , and S. Puglisi . 2010. Colored range queries and document retrieval . In String Processing and Information Retrieval. Lecture Notes in Computer Science , Vol. 6393 . Springer, 67--81. T. Gagie, G. Navarro, and S. Puglisi. 2010. Colored range queries and document retrieval. In String Processing and Information Retrieval. Lecture Notes in Computer Science, Vol. 6393. Springer, 67--81."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.041"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496839"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373","author":"Golynski A.","unstructured":"A. Golynski , I. Munro , and S. Rao . 2006. Rank\/select operations on large alphabets: A tool for text indexing . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373 . A. Golynski, I. Munro, and S. Rao. 2006. Rank\/select operations on large alphabets: A tool for text indexing. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69903-3_15"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850","author":"Grossi R.","unstructured":"R. Grossi , A. Gupta , and J. Vitter . 2003. High-order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850 . R. Grossi, A. Gupta, and J. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 678--689","author":"Grossi R.","unstructured":"R. Grossi , A. Orlandi , and R. Raman . 2010. Optimal trade-offs for succinct string indexes . In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 678--689 . R. Grossi, A. Orlandi, and R. Raman. 2010. Optimal trade-offs for succinct string indexes. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 678--689."},{"key":"e_1_2_1_25_1","unstructured":"A. Gupta W.-K. Hon R. Shah and J. Vitter. 2006. Dynamic Rank\/Select Dictionaries with Applications to XML Indexing. Technical Report CSD TR #06-014. Purdue University West Lafayette IN.  A. Gupta W.-K. Hon R. Shah and J. Vitter. 2006. Dynamic Rank\/Select Dictionaries with Applications to XML Indexing. Technical Report CSD TR #06-014. Purdue University West Lafayette IN."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.042"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_28"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.013"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"Munro I.","unstructured":"I. Munro . 1996. Tables . In Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science , Vol. 1180 . Springer , 37--42. I. Munro. 1996. Tables. In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, Vol. 1180. Springer, 37--42."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 30th International Colloquium on Algorithms, Languages, and Programming (ICALP). 345--356","author":"Munro J. I.","unstructured":"J. I. Munro , R. Raman , V. Raman , and S. S. Rao . 2003. Succinct representations of permutations . In Proceedings of the 30th International Colloquium on Algorithms, Languages, and Programming (ICALP). 345--356 . J. I. Munro, R. Raman, V. Raman, and S. S. Rao. 2003. Succinct representations of permutations. In Proceedings of the 30th International Colloquium on Algorithms, Languages, and Programming (ICALP). 345--356."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70","author":"Okanohara D.","unstructured":"D. Okanohara and K. Sadakane . 2007. Practical entropy-compressed rank\/select dictionary . In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70 . D. Okanohara and K. Sadakane. 2007. Practical entropy-compressed rank\/select dictionary. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 60--70."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_2_1_36_1","unstructured":"M. P\u0103tra\u015fcu and M. Thorup. 2008. Time-space trade-offs for predecessor search. CoRR cs\/0603043v1. http:\/\/arxiv.org\/pdf\/cs\/0603043v1.  M. P\u0103tra\u015fcu and M. Thorup. 2008. Time-space trade-offs for predecessor search. CoRR cs\/0603043v1. http:\/\/arxiv.org\/pdf\/cs\/0603043v1."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 117--122","author":"P\u0103tra\u015fcu M.","unstructured":"M. P\u0103tra\u015fcu and E. Viola . 2010. Cell-probe lower bounds for succinct partial sums . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 117--122 . M. P\u0103tra\u015fcu and E. Viola. 2010. Cell-probe lower bounds for succinct partial sums. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 117--122."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73437-6_22"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629339","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2629339"],"URL":"https:\/\/doi.org\/10.1145\/2629339","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}