Engineering the LOUDS Succinct Tree Representation
- 817 Downloads
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 2n + 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 ( parent, first-child, last-child, prev-sibling, next-sibling).
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.
Unable to display preview. Download preview PDF.
- 3.Clark, D., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proc. 7th ACM-SIAM SODA, pp. 383–391 (1996)Google Scholar
- 5.Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. In: Proc. 15th ACM-SIAM SODA, pp. 1–10 (2004)Google Scholar
- 6.Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th FOCS, pp. 549–554 (1989)Google Scholar
- 7.Kim, D.K., Na, J.C., Kim, J.E., Park, K.: Efficient implementation of Rank and Select functions for succinct representation. In: Gorodetsky, V., Liu, J., Skormin, V.A. (eds.) AIS-ADM 2005. LNCS (LNAI), vol. 3505, pp. 315–327. Springer, Heidelberg (2005)Google Scholar
- 8.Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37–42. Springer, Heidelberg (1996)Google Scholar
- 11.Martin, H.W., Orr, B.J.: A random binary tree generator. In: Proceedings of the 17th ACM Annual Computer Science Conference, pp. 33–38 (1989)Google Scholar
- 13.Centerpoint XML, http://www.cpointc.com/XML
- 14.UW XML Repository, http://www.cs.washington.edu/research/xmldatasets/