Advertisement

Engineering the LOUDS Succinct Tree Representation

  • O’Neil Delpratt
  • Naila Rahman
  • Rajeev Raman
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)

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 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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43, 275–292 (2005)CrossRefMathSciNetzbMATHGoogle Scholar
  2. 2.
    Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM Journal on Computing 34, 924–945 (2005)CrossRefMathSciNetzbMATHGoogle Scholar
  3. 3.
    Clark, D., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proc. 7th ACM-SIAM SODA, pp. 383–391 (1996)Google Scholar
  4. 4.
    Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 159–172. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  5. 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. 6.
    Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th FOCS, pp. 549–554 (1989)Google Scholar
  7. 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. 8.
    Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37–42. Springer, Heidelberg (1996)Google Scholar
  9. 9.
    Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Computing 31, 762–776 (2001)CrossRefMathSciNetzbMATHGoogle Scholar
  10. 10.
    Munro, J.I., Rao, S.S.: Succinct representations of functions. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1006–1015. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  11. 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
  12. 12.
  13. 13.
    Centerpoint XML, http://www.cpointc.com/XML
  14. 14.
  15. 15.

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • O’Neil Delpratt
    • 1
  • Naila Rahman
    • 1
  • Rajeev Raman
    • 1
  1. 1.Department of Computer ScienceUniversity of LeicesterLeicesterUK

Personalised recommendations