Succinct ordinal trees with level-ancestor queries

ABSTRACT

We consider suc cinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, i.e., 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, Proc. 30th FOCS, 549--554, 1989; Munro and Raman, SIAM J. Comput. 31 (2001), 762--776; and Benoit et. al Proc. 6th WADS, LNCS 1663, 169--180, 1999), to which we add the level-ancestor operation.Our representation takes 2n + o(n) bits to represent an n-node tree, which is within o(n) bits of the information-theoretic minimum, and supports all operations in O(1) time on the RAM model. These operations also provide a mapping from the n nodes of the tree onto the integers {1,...,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.

REFERENCES

• 1: Stephen Alstrup , Jacob Holm, Improved Algorithms for Finding Level Ancestors in Dynamic Trees, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.73-84, July 09-15, 2000
• 2: Michael A. Bender , Martin Farach-Colton, The Level Ancestor Problem Simplified, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.508-515, April 03-06, 2002
• 3: David Benoit , Erik D. Demaine , J. Ian Munro , Venkatesh Raman, Representing Trees of Higer Degree, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.169-180, August 11-14, 1999
• 4: D. A. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman and S. S. Rao. Representing trees of higher degree. TR 2001/46, Dept. of Maths & CS, University of Leicester, 2001.
• 5: Omer Berkman , Uzi Vishkin, Finding level-ancestors in trees, Journal of Computer and System Sciences, v.48 n.2, p.214-230, April 1994 [doi>10.1016/S0022-0000(05)80002-9]
• 6: B. Chazelle. Computing on a free tree via complexity-preserving mappings. A lgorithmica 2 (1987), pp. 337--361.
• 7: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 8: J. Clark and S. DeRose. XML Path Language (XPath) Version 1.0. W3C Recommendation 16 November 1999. http://www.w3.org/TR/xpath. W3C Consortium, 1999.
• 9: P. F. Dietz. Finding level-ancestors in dynamic trees. In Proc. 2nd WADS, LNCS 519, pp. 32--40, 1991.
• 10: Martin Farach , S. Muthukrishnan, Perfect Hashing for Strings: Formalization and Algorithms, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.130-140, June 10-12, 1996
• 11: A. Le Hors, P. Le Hégaret, L. Wood, G. Nicol, J. Robie, M. Champion, S. Byrne. Document Object Model (DOM) Level 2 Core Specification Version 1.0. W3C Recommendation 13 November, 2000. http://www.w3.org/TR/DOM-Level-2-Core. W3C Consortium, 2000.
• 12: G. Jacobson. Space-efficient static trees and graphs. In Proc. 30th FOCS, pp. 549--554, 1989.
• 13: J. Ian Munro, Tables, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-42, December 18-20, 1996
• 14: J. Ian Munro , Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, v.31 n.3, p.762-776, 2001 [doi>10.1137/S0097539799364092]
• 15: J. I. Munro and S. S. Rao. Succinct representations of functions. Manuscript, 2003.
• 16: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California