| Presentation | 2006-09-26 A New Representation of Ordered Trees Jesper JANSSON, Kunihiko SADAKANE, Wing-Kin SUNG, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 matches the information-theoretic lower bound. Many fundamental operations on trees can be done in constant time on word RAM, for example finding parent, the first child, 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | succinct data structures / entropy / ordered trees |
| Paper # | COMP2006-29 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/9/19(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A New Representation of Ordered Trees |
| Sub Title (in English) | |
| Keyword(1) | succinct data structures |
| Keyword(2) | entropy |
| Keyword(3) | ordered trees |
| 1st Author's Name | Jesper JANSSON |
| 1st Author's Affiliation | Department of Computer Science and Communication Engineering, Kyushu University() |
| 2nd Author's Name | Kunihiko SADAKANE |
| 2nd Author's Affiliation | Department of Computer Science and Communication Engineering, Kyushu University |
| 3rd Author's Name | Wing-Kin SUNG |
| 3rd Author's Affiliation | School of Computing, National University of Singapore |
| Date | 2006-09-26 |
| Paper # | COMP2006-29 |
| Volume (vol) | vol.106 |
| Number (no) | 258 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |