Name
Abstract | ||
|---|---|---|
We propose a uniform approach for succinct representation of various families of trees. The method is based on two recursive decomposition of trees into subtrees. Recursive decomposition of a structure into substructures is a common technique in succinct data structures and has been shown fruitful in succinct representation of ordinal trees [7,10] and dynamic binary trees [16,21]. We take an approach that simplifies the existing representation of ordinal trees while allowing the full set of navigational operations. The approach applied to cardinal (i.e. k-ary) trees yields a space-optimal succinct representation allowing cardinal-type operations (e.g. determining child labeled i) as well as the full set of ordinal-type operations (e.g. reporting the number of siblings to the left of a node). Existing space-optimal succinct representations had not been able to support both types of operations [2,19].We demonstrate how the approach can be applied to obtain a space-optimal succinct representation for the family of free trees where the order of children is insignificant. Furthermore, we show that our approach can be used to obtain entropy-based succinct representations. We show that our approach matches the degree-distribution entropy suggested by Jansson etal. [13]. We discuss that our approach can be made adaptive to various other entropy measures. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69903-3_17 | SWAT |
Keywords | Field | DocType |
uniform approach,succinct representation,ordinal tree,entropy-based succinct representation,full set,uniform approach towards succinct,succinct data structure,space-optimal succinct representation,trees yield,existing representation,recursive decomposition,binary tree,degree distribution | Discrete mathematics,Lookup table,Combinatorics,Succinct data structure,Computer science,Ordinal number,Binary tree,Algorithm,Wavelet Tree,Recursive decomposition | Conference |
Volume | ISSN | Citations |
5124 | 0302-9743 | 25 |
PageRank | References | Authors |
1.04 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Farzan | 1 | 136 | 11.07 |
| J. Ian Munro | 2 | 3010 | 462.97 |