Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Engineering the LOUDS Succinct Tree Representation
| |
|
Session 5
Engineering the LOUDS Succinct Tree Representation
O’Neil Delpratt1  , Naila Rahman1 and Rajeev Raman1
| (1) |
Department of Computer Science, University of Leicester, Leicester LE1 7RH, UK |
Abstract
Ordinal trees are arbitrary rooted trees where the children of each node are ordered. We consider succinct, or highly space-efficient, representations of (static) ordinal trees with n nodes that use 2 n + o( n) bits of space to represent ordinal trees. There are a number of such representations: each supports a different set of tree
operations in O(1) time on the RAM model.
In this paper we focus on the practical performance the fundamental Level-Order Unary Degree Sequence (LOUDS) representation
[Jacobson, Proc. 30th FOCS, 549–554, 1989]. Due to its conceptual simplicity, LOUDS would appear to be a representation with good practical performance.
A tree can also be represented succinctly as a balanced parenthesis sequence [Munro and Raman, SIAM J. Comput. 31 (2001), 762–776; Jacobson, op. cit.; Geary et al. Proc. 15th CPM Symp., LNCS 3109, pp. 159–172, 2004]. In essence, the two representations are complementary, and have only the basic navigational
operations in common (  ,  ,  ,  ,  )
Unfortunately, a naive implementation of LOUDS is not competitive with the parenthesis implementation of Geary et al. on
the common set of operations. We propose variants of LOUDS, of which one, called LOUDS++, is competitive with the parenthesis representation. A motivation is the succinct representation of large static XML documents,
and our tests involve traversing XML documents in various canonical orders.
Delpratt is supported by PPARC e-Science Studentship PPA/S/E/2003/03749.
Fulltext Preview (Small, Large)
|
|
|
|
|
|