PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully-Functional Static and Dynamic Succinct Trees

Gonzalo Navarro, Kunihiko Sadakane

arXiv:0905.0768v5cs.DS

TL;DR

Existing ordinal-tree representations face space costs or limited operations, while powerful static structures are difficult to dynamize. This paper introduces range min-max trees as a simple foundation for succinct static and dynamic trees, dynamic sequences, and bitmaps, achieving improved space and time bounds.

  • Problem

    Pointer-based tree representations require Θ(n log n) bits, while existing succinct representations differ in supported operations, motivating simpler and more capable designs.

  • Method

    The paper uses range min-max trees to reduce tree operations to a few constant-time primitives on polylogarithmic subtrees and extends this framework to larger structures.

  • Results

    The resulting representations use 2n+O(n/polylog(n)) bits for static trees, while dynamic structures achieve 2n+O(n log log n/log n) bits with O(log n/log log n) time for most operations.

  • Takeaways & Limitations

    The techniques also support dynamic compressed sequences and bitmaps within zero-order entropy bounds, with optimal-time operations for polylog-sized alphabets.

  • Takeaways & Limitations

    O(log n/log log n) time is not achieved for all dynamic tree operations, and the optimality of the associated redundancy remains unclear.

Abstract

from arXiv · show

We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + o(n)$ bits and a number of operations on the tree can be supported in constant time under the word-RAM model. However the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving $2n + O(n /\polylog(n))$ bits of space. The redundancy is significantly lower than any previous proposal. Our data structure builds on the range min-max tree to achieve $2n+O(n/\log n)$ bits of space and $O(\log n)$ time for all the operations. We also propose an improved data structure using $2n+O(n\log\log n/\log n)$ bits and improving the time to the optimal $O(\log n/\log \log n)$ for most operations. Furthermore, we support sophisticated operations that allow attaching and detaching whole subtrees, in time $\Order(\log^{1+ε} n / \log\log n)$. Our techniques are of independent interest. One allows representing dynamic bitmaps and sequences supporting rank/select and indels, within zero-order entropy bounds and optimal time $O(\log n / \log\log n)$ for all operations on bitmaps and polylog-sized alphabets, and $O(\log n \log σ/ (\log\log n)^2)$ on larger alphabet sizes $σ$. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.

1 Introduction

The paper introduces succinct ordinal-tree representations built around a range min-max tree, targeting compact space, broad operation support, and dynamic updates. It also derives applications to dynamic sequences, bitmaps, and compressed representations.

  • Static succinct trees: 2n + O(n / log^c n) bits supports all static ordinal-tree operations except insert and delete in constant time.The structure is constructible from the balanced-parentheses sequence in O(n) time using O(n) bits.
  • Core approach: The range min-max tree reduces tree queries to a few bit-vector primitives instead of separate auxiliary structures for each operation.This design supports a simple dynamic extension and lowers redundancy relative to previous representations.
  • Dynamic succinct trees: 2n + O(n log log n / log n) bits supports dynamic ordinal-tree operations within the worst-case complexities of Table 1.Alternatively, all operations run in O(log n) time using 2n + O(n / log n) bits.
  • Dynamic succinct trees: O(log n / log log n) time is achieved for most dynamic tree operations, including insert and delete, and is optimal for the supported basic-operation-plus-update set.Degree, child, and child rank can instead be handled in O(log n) time.
  • Dynamic succinct trees: Whole subtrees can be attached and detached in O(log^{1+ε} n) time for any constant ε > 0.These operations had not previously been considered in succinct tree representations.
  • Byproducts: Dynamic bitmaps and sequences achieve zero-order entropy space with rank, select, and indels, including optimal O(log n / log log n) time for bitmaps and polylogarithmic alphabets.The sequence result also applies to compressed text indexes and compressed-space Burrows-Wheeler-transform construction.

2 Preliminaries

The preliminaries introduce succinct representations, balanced-parentheses encoding, and dynamic bitmap and sequence problems that motivate the paper’s contributions.

  • Ordinal trees: Ordinal trees can be encoded as balanced parentheses, with each node represented by matching parentheses and subtrees ordered between them.The opening-parenthesis position identifies the node.
  • Ordinal trees: Existing static ordinal-tree representations support broad functionality near 2n bits, while dynamic approaches support only more limited operation sets.The paper positions its representations against these functionality and dynamization gaps.
  • Dynamic compressed bitmaps and sequences: Dynamic bitmaps and sequences require rank, select, insertions, and deletions under compressed-space and time constraints.Prior work achieved O(log n / log log n) time for dynamic bitmaps, while sequence bounds depend on alphabet size and compression overhead.
  • Dynamic compressed bitmaps and sequences: The paper targets optimal O(log n / log log n) time for polylogarithmic alphabets and reduces compressed-space lower-order terms by a Θ(log log n) factor.The stated improvements also apply to dynamic text collections, compressed indexes, and Burrows-Wheeler transform construction.

3 Fundamental concepts

The paper encodes parentheses as bit vectors and unifies tree navigation and sequence operations through excess sums and a small set of search and range-query primitives.

  • Excess array: The excess array E is the prefix sum under π(1)=1 and π(0)=−1, recording opening-minus-closing parentheses and changing by one between positions.At opening parentheses, E gives node depth; at closing parentheses, it gives depth minus 1.
  • Tree navigation: findclose, findopen, enclose, and level ancestor reduce to forward or backward searches for specified excess-sum values.For example, findclose is fwd search(P, π, i, 0), while enclose uses a backward search with target sum 2.
  • Unified primitives: Rank and select on bit vectors are unified with parentheses operations through the functions φ and ψ, while most remaining operations reduce to eight primitives.The primitive set includes forward/backward search, sum, range minima/maxima, degree, child, and child rank.
  • Range min-max tree: A range min-max tree partitions the vector into leaves and stores last, minimum, and maximum prefix-sum values at leaves and internal nodes.With g=π, the stored minima and maxima describe excess values over corresponding intervals.

4 A simple data structure for polylogarithmic-size trees

For polylogarithmic-size vectors, the range min-max tree and universal lookup tables support the paper’s core searches and range queries in O(c) time with compact space.

  • Tree construction: The structure partitions the vector into chunks and uses a complete k-ary tree with k = Θ(w/(c log w)), giving depth O(c).Leaves store chunk summaries, while heap-like arrays store e′, m′, and M′ values.
  • Range decomposition and search: Any queried interval decomposes into O(ck) subranges, and sibling-sequence lookup reduces the search from O(ck) to O(c).Universal tables identify the first sibling whose minimum or maximum interval contains the target value.
  • Range decomposition and search: Table lookup handles searches within chunks in constant time before the tree searches the relevant right-sibling subranges.The global target is derived from the prefix value at the chunk boundary and the within-chunk sum.
  • Primitive operations: O(c) time supports fwd search, bwd search, sum, rmqi, and RMQi on vectors of length n < w^c using universal tables requiring O(2^w log w) bits.The same asymptotic bound is stated for both search/sum operations and range minimum/maximum queries.
  • Space reduction: Theorem 4 represents N = B^c parentheses using N + 2 bits in the data structure while supporting all Table 1 operations in O(c) time.This holds on a w-bit word RAM for c > 3/2 and sufficiently small B = Θ(w^(c/log w)).

5 A data structure for large trees

The section extends range min-max-tree techniques from sufficiently small trees to arbitrary-size trees, supporting searches and related operations with compact space. It organizes block minima and maxima through left-to-right-minimum sequences and weighted ancestor queries, obtaining linear preprocessing and logarithmic-time operations.

  • O(log n) time supports all operations on arbitrary-size trees using an extremely simple range min-max-tree data structure.The construction uses k = w/log n and achieves this bound for all operations.
  • Searches across blocks: Blocks of the parentheses sequence store minima, maxima, and excess values, enabling searches to identify a candidate block before completing the query locally.Large trees are divided into blocks of length w^c, and each block is handled by a range min-max tree.
  • Searches across blocks: Left-to-right-minimum sequences reduce first-threshold searches to sequence positions, while coincident suffixes allow their compact representation in a trie-like tree.The resulting T_lrm tree has one node per block and paths spelling the corresponding lrm sequences.
  • Weighted searches: Weighted level-ancestor queries on T_lrm find the first qualifying block by converting value differences into weighted ancestor distances.The edge weight from j to its parent is m_j − m_j1, and the relevant weight is at most w^c.
  • Complexity: O(n) preprocessing and O(c + t) query time follow after choosing ε = min(1/2, 1/c) for c > 3/2.The reported data-structure size is O(n log^2 n/w^c + n^t t log^t n + n^3/4) bits.
  • Complexity: 2n + O(n(c log log n)^c/log^(c−2) n) bits and O(c) time per operation result from setting w = log n, t = c, and B = O(log^c n/(c log log n)).The construction time is O(n).

6 A simple data structure for dynamic trees

The dynamic structure stores the balanced-parentheses sequence in a dynamic min-max tree whose leaves maintain packed segments. It supports updates and tree queries with either logarithmic time and lower redundancy or the faster complexities stated in the theorem.

  • Representation: Leaves store verbatim segments of the parentheses vector with lengths between L and 2L, while internal nodes maintain aggregate excess, minima, maxima, and minimum counts.For the simple logarithmic-time structure, L = log^2 n.
  • Updates: Segment scans, local searches, and migrations take O(L/log n) time by processing Θ(log n)-bit chunks with universal tables.This supports dynamic maintenance while preserving the segment-length invariant.
  • 2n + O(n/log n) bits support all dynamic tree queries and updates in O(log n) worst-case time.This representation is built from a dynamic range min-max tree over the balanced-parentheses vector.
  • Space: O(n/log n) redundancy follows because each internal node stores O(log n) bits and there are O(n/L) nodes, including the leaf-data overhead.The universal tables add O(√n · polylog(n)) bits, which is negligible.
  • Updates: Insertions and deletions update the modified leaf and then recompute stored aggregate values along the path to the root.Balancing operations split, concatenate, or redistribute neighboring segments while maintaining lengths from L to 2L.

7 A faster dynamic data structure

The faster dynamic structure replaces the balanced binary tree with a B-tree range min-max tree, reducing height and supporting broad tree operations with succinct space. It provides an alternative trade-off between O(log n) time with lower redundancy and faster operations with somewhat larger redundancy.

  • Structure: A B-tree with branching factor Θ(√log n) replaces the balanced binary tree, yielding depth O(log n / log log n).The range min-max tree stores cumulative boundaries, sums, excesses, minima, maxima, and minimum counts for each child.
  • Complexity trade-offs: 2n+O(n log log n / log n) bits supports forward and backward search in O(log n) time and most other queries and updates in O(log n / log log n) time.Degree, child, child rank, and updates can instead be handled in O(log n) time under the same space bound.
  • Operations: O(log n / log log n) applications of local primitives support rank, select, depth, forward and backward search, and range-minimum queries.Searches group relevant B-tree nodes into consecutive sibling sequences, while range-minimum queries recurse through at most the tree depth.
  • Complexity trade-offs: O(log n / log log n) time supports most queries and updates, while degree, child, and child rank require O(log n) time in the faster-space variant.The alternative supports all listed operations, including updates, in O(log n) time.
  • Complexity trade-offs: 2n+O(n / log n) bits supports all operations in O(log n) time, and the section’s theorem summarizes this alternative succinct dynamic representation.The construction and maintenance procedures account for node splitting, rebuilding, and updates within the stated bounds.
  • Whole-subtree updates: Subtree detachment repairs underfull nodes on the detached tree’s boundary by merging with siblings and splitting when necessary in O(log1+ϵ n) time.Changing the tree degree to Θ(log^ϵ n) handles dangling-cursor complications while multiplying query times by O(1/ϵ).

8 Improving dynamic compressed sequences

The paper extends its range min-max tree techniques to dynamic compressed sequences and bitmaps. The resulting structures preserve entropy-bounded space while supporting updates and queries efficiently, with applications to compressed text indexes and BWT construction.

  • Sequence framework: The techniques improve prior results for sequences of numbers with sum and search operations and match known lower bounds.They also serve as building blocks for dynamic compressed bitmaps and related sequence structures.
  • Codes, numbers, and partial sums: O(log n / log log n) time supports access, sum, search, modification, insertion, and deletion of O(log n)-bit codes.Codes are stored whole in leaves, while internal nodes maintain subtree counts and sums for navigation.
  • Dynamic bitmaps: nH0(B)+O(n log log n / log n) bits supports bitmap rank, select, insertion, and deletion in O(log n / log log n) time.The bitmap is compressed using variable-length chunks represented by class, offset, and chunk-length information.
  • Dynamic bitmaps: The chunk invariant bi + bi+1 > b limits insertion-induced leaf growth to O(log n) bits while keeping overhead O(n log log n / log n).Allowing chunk lengths 1 ≤ bi ≤ b avoids the alignment-growth problem of fixed-size chunks.
  • Dynamic bitmaps: O(log1+ϵ n) time supports attachment and detachment of contiguous compressed bitmaps while retaining zero-order compression.Arbitrary cut positions are handled by splitting compressed codes.
  • Applications: The results support compressed dynamic text collections and compressed-space construction of the BWT and Alphabet-Friendly FM-index.For the BWT, construction uses nHh(T)+o(n log σ) bits and runs in O(n log n log log n(1 + log σ log log n)) time.
  • Applications: For polylog-sized alphabets, the BWT is built in o(n log n) time, while for σ=Θ(n) it is built in o(n log^2 n) time.The latter improves the corresponding previous result by a log log n factor.

9 Concluding remarks

The paper presents succinct ordinal-tree structures that combine near-optimal space with broad static and dynamic operation support. Its range min-max-tree approach also yields practical implementations and applications to dynamic sequences and compressed text indexing.

  • Static case: 2n + O(n/polylog(n)) bits supports all known static-tree operations in constant time.The range min-max tree reduces operations to a handful of constant-time primitives on polylog-sized subtrees.
  • Static case: Around 2.37 bits per node delivered most operations within the microsecond on a standard PC and was smallest and fastest in most tested cases.The implementation also provided the widest coverage of operations in comparisons with state-of-the-art representations.
  • Dynamic case: O(log n) time supports all dynamic-tree operations, including node insertion, deletion, and attaching or detaching whole subtrees.A variant supports most operations in O(log n / log log n) time, which is optimal for several basic dynamic-tree operations.
  • Applications: Dynamic compressed sequences achieve zero-order entropy space and O(log n / log log n) time for polylog-sized alphabets.These results improve operation times and provide applications to compressed text indexing.
  • Open questions: The static redundancy is optimal for some operations, while optimality of the dynamic redundancy and all-operation time bounds remains unresolved.The paper identifies open questions about lower bounds for fundamental balanced-parentheses operations and achieving O(log n / log log n) time for every dynamic-tree operation.
Loading 0905.0768v5…