Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/1837
Title: Succinct ordinal trees with level-ancestor queries
Authors: Geary, Richard F.
Raman, Rajeev
Raman, V.
First Published: 2006
Citation: ACM Transactions on Algorithms, 2006, 2 (4), pp.510-534
Abstract: We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal 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 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.
DOI Link: 10.1145/1198513.1198516
ISSN: 1549-6325
Links: http://dl.acm.org/citation.cfm?doid=1198513.1198516
http://hdl.handle.net/2381/1837
Type: Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.