{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:05Z","timestamp":1759638305296,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"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":[[2011,9]]},"abstract":"<jats:p>We define and design succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an extended set of operations using the basic operators defined in the ADT. The main advantage of succinct indexes as opposed to succinct (integrated data\/index) encodings is that we make assumptions only on the ADT through which the main data is accessed, rather than the way in which the data is encoded. This allows more freedom in the encoding of the main data. In this article, we present succinct indexes for various data types, namely strings, binary relations and multilabeled trees. Given the support for the interface of the ADTs of these data types, we can support various useful operations efficiently by constructing succinct indexes for them. When the operators in the ADTs are supported in constant time, our results are comparable to previous results, while allowing more flexibility in the encoding of the given data.<\/jats:p>\n          <jats:p>\n            Using our techniques, we design a succinct encoding that represents a string of length\n            <jats:italic>n<\/jats:italic>\n            over an alphabet of size \u03c3 using\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>S<\/jats:italic>\n            ) + lg \u03c3 \u00b7\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            lg \u03c3\/lg lg lg \u03c3) bits to support access\/rank\/select operations in\n            <jats:italic>o<\/jats:italic>\n            ((lg lg \u03c3)\n            <jats:sup>1+\u03f5<\/jats:sup>\n            ) time, for any fixed constant \u03f5 &gt; 0. We also design a succinct text index using\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            (\n            <jats:italic>S<\/jats:italic>\n            ) +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            lg \u03c3\/lg lg \u03c3) bits that supports finding all the occ occurrences of a given pattern of length\n            <jats:italic>m<\/jats:italic>\n            in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            lg lg \u03c3 + occ lg\n            <jats:italic>n<\/jats:italic>\n            \/lg\n            <jats:sup>\u03f5<\/jats:sup>\n            \u03c3) time, for any fixed constant 0 &lt; \u03f5 &lt; 1. Previous results on these two problems either have a lg \u03c3 factor instead of lg lg \u03c3 in the running time, or are not compressed. Finally, we present succinct encodings of binary relations and multi-labeled trees that are more compact than previous structures.\n          <\/jats:p>","DOI":"10.1145\/2000807.2000820","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Succinct indexes for strings, binary relations and multilabeled trees"],"prefix":"10.1145","volume":"7","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[{"name":"University of Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[{"name":"Seoul National University, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"volume-title":"Adaptive search algorithm for patterns, in succinctly encoded XML. Tech. rep. CS-2006-11","author":"Barbay J.","key":"e_1_2_1_1_1","unstructured":"Barbay , J. 2006. Adaptive search algorithm for patterns, in succinctly encoded XML. Tech. rep. CS-2006-11 , University of Waterloo , Ontario, Canada . Barbay, J. 2006. Adaptive search algorithm for patterns, in succinctly encoded XML. Tech. rep. CS-2006-11, University of Waterloo, Ontario, Canada."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.015"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689","author":"Barbay J.","key":"e_1_2_1_3_1","unstructured":"Barbay , J. , He , M. , Munro , J. I. , and Rao , S. S . 2007. Succinct indexes for strings, binary relations and multi-labeled trees . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689 . Barbay, J., He, M., Munro, J. I., and Rao, S. S. 2007. Succinct indexes for strings, binary relations and multi-labeled trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1146-6"},{"volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391","author":"Clark D. R.","key":"e_1_2_1_5_1","unstructured":"Clark , D. R. and Munro , J. I . 1996. Efficient suffix trees on secondary storage . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391 . Clark, D. R. and Munro, J. I. 1996. Efficient suffix trees on secondary storage. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_12"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00043-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082043"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.69"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 11th Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science","volume":"3246","author":"Ferragina P.","unstructured":"Ferragina , P. , Manzini , G. , M\u00e4kinen , V. , and Navarro , G . 2004. An alphabet-friendly FM-index . In Proceedings of the 11th Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science , vol. 3246 . Springer-Verlag, 150--160. Ferragina, P., Manzini, G., M\u00e4kinen, V., and Navarro, G. 2004. An alphabet-friendly FM-index. In Proceedings of the 11th Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science, vol. 3246. Springer-Verlag, 150--160."},{"volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 332--344","author":"G\u00e1l A.","key":"e_1_2_1_12_1","unstructured":"G\u00e1l , A. and Miltersen , P. B . 2003. The cell probe complexity of succinct data structures . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 332--344 . G\u00e1l, A. and Miltersen, P. B. 2003. The cell probe complexity of succinct data structures. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 332--344."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198516"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756553.1756563"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.041"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109599"},{"key":"e_1_2_1_17_1","first-page":"66","article-title":"New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures & Algorithms. Prentice-Hall","volume":"5","author":"Gonnet G. H.","year":"1992","unstructured":"Gonnet , G. H. , Baeza-Yates , R. A. , and Snider , T. 1992 . New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures & Algorithms. Prentice-Hall , Chapter 5 , 66 -- 82 . Gonnet, G. H., Baeza-Yates, R. A., and Snider, T. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures & Algorithms. Prentice-Hall, Chapter 5, 66--82.","journal-title":"Chapter"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_27"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850","author":"Grossi R.","key":"e_1_2_1_19_1","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. 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. 841--850."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","key":"e_1_2_1_21_1","unstructured":"Gusfield , D. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge University Press , Cambridge, UK . Gusfield, D. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, UK."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 23--32","author":"He M.","key":"e_1_2_1_23_1","unstructured":"He , M. , Munro , J. I. , and Rao , S. S . 2005. A categorization theorem on suffix arrays with applications to space efficient text indexes . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 23--32 . He, M., Munro, J. I., and Rao, S. S. 2005. A categorization theorem on suffix arrays with applications to space efficient text indexes. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 23--32."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_25_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 Annual 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 Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 11--12","author":"Miltersen P. B.","year":"2005","unstructured":"Miltersen , P. B. 2005 . Lower bounds on the size of selection and rank indexes . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 11--12 . Miltersen, P. B. 2005. Lower bounds on the size of selection and rank indexes. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 11--12."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 618--627","author":"Mortensen C. W.","year":"2003","unstructured":"Mortensen , C. W. 2003 . Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 618--627 . Mortensen, C. W. 2003. Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 618--627."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436722"},{"volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 345--356","author":"Munro J. I.","key":"e_1_2_1_30_1","unstructured":"Munro , J. I. , Raman , R. , Raman , V. , and Rao , S. S . 2003. Succinct representations of permutations . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 345--356 . Munro, J. I., Raman, R., Raman, V., and Rao, S. S. 2003. Succinct representations of permutations. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 345--356."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109693"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.178"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000820","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000807.2000820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:03Z","timestamp":1750244403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2000807.2000820"],"URL":"https:\/\/doi.org\/10.1145\/2000807.2000820","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2008-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}