{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:44Z","timestamp":1767339764238},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>\n            We consider\n            <jats:italic>succinct<\/jats:italic>\n            or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static\n            <jats:italic>ordinal<\/jats:italic>\n            trees, that is, arbitrary static rooted trees where the children of each node are ordered. The set of operations is essentially the union of the sets of operations supported by previous succinct representations [Jacobson 1989; Munro and Raman 2001; Benoit et al. 1999] to which we add the\n            <jats:italic>level-ancestor<\/jats:italic>\n            operation.Our representation takes 2\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits to represent an\n            <jats:italic>n<\/jats:italic>\n            -node tree, which is within\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits of the information-theoretic minimum, and supports all operations in\n            <jats:italic>O<\/jats:italic>\n            (1) time on the RAM model. These operations also provide a mapping from the\n            <jats:italic>n<\/jats:italic>\n            nodes of the tree onto the integers {1, \u2026,\n            <jats:italic>n<\/jats:italic>\n            }. In addition to the existing motivations for studying such data structures, we are motivated by the problem of representing XML documents compactly so that XPath queries can be supported efficiently.\n          <\/jats:p>","DOI":"10.1145\/1198513.1198516","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"510-534","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["Succinct ordinal trees with level-ancestor queries"],"prefix":"10.1145","volume":"2","author":[{"given":"Richard F.","family":"Geary","sequence":"first","affiliation":[{"name":"University of Leicester, Leicester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[{"name":"University of Leicester, Leicester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"73","volume-title":"27th International Colloquium, ICALP 2000, Proceedings. Lecture Notes in Computer Science","volume":"1853","author":"Alstrup S.","unstructured":"Alstrup , S. , and Holm , J . 2000. Improved algorithms for finding level ancestors in dynamic trees. In Automata, Languages and Programming , 27th International Colloquium, ICALP 2000, Proceedings. Lecture Notes in Computer Science , vol. 1853 . Springer-Verlag, New York , pp. 73 -- 84 .]] Alstrup, S., and Holm, J. 2000. Improved algorithms for finding level ancestors in dynamic trees. In Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Proceedings. Lecture Notes in Computer Science, vol. 1853. Springer-Verlag, New York, pp. 73--84.]]"},{"key":"e_1_2_1_2_1","volume-title":"Apache Xindice: Frequently Asked Questions","author":"Apache Software Foundation","year":"2005","unstructured":"Apache Software Foundation . 2005 . Apache Xindice: Frequently Asked Questions . http:\/\/xml.apache.org\/xindice\/faq.html, October.]] Apache Software Foundation. 2005. Apache Xindice: Frequently Asked Questions. http:\/\/xml.apache.org\/xindice\/faq.html, October.]]"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","first-page":"508","volume-title":"LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Proceedings","author":"Bender M. A.","unstructured":"Bender , M. A. , and Farach-Colton , M. 2002. The level ancestor problem simplified . In LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Proceedings . Lecture Notes in Computer Science , vol. 2286 . Springer-Verlag , New York , pp. 508 -- 515 .]] Bender, M. A., and Farach-Colton, M. 2002. The level ancestor problem simplified. In LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Proceedings. Lecture Notes in Computer Science, vol. 2286. Springer-Verlag, New York, pp. 508--515.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_5_1","first-page":"169","volume-title":"6th International Workshop, WADS '99, Proceedings. Lecture Notes in Computer Science","volume":"1663","author":"Benoit D. A.","unstructured":"Benoit , D. A. , Demaine , E. D. , Munro , J. I. , and Raman , V . 1999. Representing trees of higher degree. In Algorithms and Data Structures , 6th International Workshop, WADS '99, Proceedings. Lecture Notes in Computer Science , vol. 1663 . Springer-Verlag, New York , pp. 169 -- 180 .]] Benoit, D. A., Demaine, E. D., Munro, J. I., and Raman, V. 1999. Representing trees of higher degree. In Algorithms and Data Structures, 6th International Workshop, WADS '99, Proceedings. Lecture Notes in Computer Science, vol. 1663. Springer-Verlag, New York, pp. 169--180.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80002-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840366"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411381"},{"key":"e_1_2_1_9_1","first-page":"383","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Clark D.","unstructured":"Clark , D. , and Munro , J. I . 1996. Efficient suffix trees on secondary storage (extended Abstract) . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 383 -- 391 .]] Clark, D., and Munro, J. I. 1996. Efficient suffix trees on secondary storage (extended Abstract). In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 383--391.]]"},{"key":"e_1_2_1_10_1","unstructured":"Clark J. and Derose S. 1999. XML path language (XPath) Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/xpath W3C Consortium.]]  Clark J. and Derose S. 1999. XML path language (XPath) Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/xpath W3C Consortium.]]"},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","first-page":"32","volume-title":"Algorithms and Data Structures, 2nd Workshop WADS '91, Proceedings","author":"Dietz P. F.","unstructured":"Dietz , P. F. 1991. Finding level-ancestors in dynamic trees . In Algorithms and Data Structures, 2nd Workshop WADS '91, Proceedings . Lecture Notes in Computer Science , vol. 519 . Springer-Verlag , New York , pp. 32 -- 40 .]] Dietz, P. F. 1991. Finding level-ancestors in dynamic trees. In Algorithms and Data Structures, 2nd Workshop WADS '91, Proceedings. Lecture Notes in Computer Science, vol. 519. Springer-Verlag, New York, pp. 32--40.]]"},{"key":"e_1_2_1_12_1","first-page":"130","volume-title":"7th Annual Symposium, CPM 96, Proceedings. Lecture Notes in Computer Science","volume":"1075","author":"Farach M.","unstructured":"Farach , M. , and Muthukrishnan , S . 1996. Perfect hashing for strings: formalization and algorithms. In Combinatorial Pattern Matching , 7th Annual Symposium, CPM 96, Proceedings. Lecture Notes in Computer Science , vol. 1075 . Springer-Verlag, New York , pp. 130 -- 140 .]] Farach, M., and Muthukrishnan, S. 1996. Perfect hashing for strings: formalization and algorithms. In Combinatorial Pattern Matching, 7th Annual Symposium, CPM 96, Proceedings. Lecture Notes in Computer Science, vol. 1075. Springer-Verlag, New York, pp. 130--140.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.69"},{"key":"e_1_2_1_14_1","unstructured":"Le Hors A. Le H\u00e9garet P. Wood L. Nicol G. Robie J. Champion M. and Byrne S. 2000. Document object model (DOM) level 2 core specification Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/DOM-Level-2-Core W3C Consortium.]]  Le Hors A. Le H\u00e9garet P. Wood L. Nicol G. Robie J. Champion M. and Byrne S. 2000. Document object model (DOM) level 2 core specification Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/DOM-Level-2-Core W3C Consortium.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Munro J. I. and \n      Rao S. S\n  . \n  2004\n  . Succinct representations of functions. In Proceedings of the 31st International Colloquium on Automata Languages and Computation Lecture Notes in Computer Science vol. \n  3142 Springer-Verlag New York pp. \n  1006\n  --\n  1015\n  .]]  Munro J. I. and Rao S. S. 2004. Succinct representations of functions. In Proceedings of the 31st International Colloquium on Automata Languages and Computation Lecture Notes in Computer Science vol. 3142 Springer-Verlag New York pp. 1006--1015.]]","DOI":"10.1007\/978-3-540-27836-8_84"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","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 Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 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 Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 233--242.]]"},{"key":"e_1_2_1_19_1","volume-title":"Rudin, W. 1987. Real & Complex Analysis","unstructured":"Rudin, W. 1987. Real & Complex Analysis , 3 rd ed. McGraw-Hill , Englewood, Cliffs , N.J.]] Rudin, W. 1987. Real & Complex Analysis, 3rd ed. McGraw-Hill, Englewood, Cliffs, N.J.]]","edition":"3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:32:30Z","timestamp":1672259550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198516"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198516","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}