Ultra-succinct representation of ordered trees

Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

53 Citations (Scopus)

Abstract

and the Society for Industrial and Applied Mathematics. There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis) [Munro, Raman 2001] and DFUDS (depth first unary degree sequence) [Benoit et al. 2005]. Both have size 2n+o(n) bits for n-node trees, which asymptotically matches the information-theoretic lower bound. Many fundamental operations on trees can be done in constant time on word RAM, for example finding the parent, the first child, the next sibling, the number of descendants, etc. However there has been no single representation supporting every existing operation in constant time; BP does not support i-th child, while DFUDS does not support lca (lowest common ancestor). In this paper, we give the first succinct tree representation supporting every one of the fundamental operations previously proposed for BP or DFUDS along with some new operations in constant time. Moreover, its size surpasses the information-theoretic lower bound and matches the entropy of the tree based on the distribution of node degrees. We call this an ultra-succinct data structure. As a consequence, a tree in which every internal node has exactly two children can be represented in n + o(n) bits. We also show applications for ultra-succinct compressed suffix trees and labeled trees.
Original languageEnglish
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages575-584
Number of pages10
Volume07-09-January-2007
ISBN (Electronic)9780898716245
Publication statusPublished - 1 Jan 2007
Externally publishedYes
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: 7 Jan 20079 Jan 2007

Conference

Conference18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Country/TerritoryUnited States
CityNew Orleans
Period7/01/079/01/07

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this