Dynamic "Succincter"

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work “succincter” by Pǎtraşcu [1] showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its depth. It has been a versatile building block for constructing succinct data structures, including rank/select data structures, dictionaries, locally decodable arithmetic coding, storing balanced parenthesis, etc. In this paper, we show how to “dynamize” an aB-tree. Our main result is the design of dynamic aB-trees (daB-trees) with branching factor two using only three bits of redundancy (with the help of lookup tables that are of negligible size in applications), while supporting updates and queries in time polynomial in its depth. As an application, we present a dynamic rank/select data structure for n-bit arrays, also known as a dynamic fully indexable dictionary (FID) [2]. It supports updates and queries in $O(\log n / \log \log n)$ time, and when the array has m ones, the \begin{equation*}\log \begin{pmatrix}n \\m\end{pmatrix}+On / 2^{\log 0. 199} n\end{equation*}bits. Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks [3]. Prior to our work, no dynamic FID with near-optimal update and query times and redundancy $o(n / \log n)$ was known. We further show that a dynamic sequence supporting insertions, deletions and rank/select queries can be maintained in (optimal) $O(\log n / \log \log n)$ time and with $O\left(n \cdot \operatorname{poly} \log \log n / \log ^{2} n\right)$ bits of redundancy.

Authors

• Tianxiao Li
• Jingxun Liang
• Huacheng Yu
• Renfei Zhou

Keywords

• Computer science
• Dictionaries
• Redundancy
• Encoding
• Arrays
• Arithmetic
• Data Structure
• Lookup Table
• Update Time
• Query Time
• Arithmetic Coding
• Decoding
• Running Time
• Time Constant
• Alphabet
• Linear Time
• Tree Height
• Leaf Node
• Subtree
• Tree Level
• Space Usage
• String Length
• Lowest Common Ancestor
• Node Labels
• Update Algorithm
• Zero Padding
• Dynamic Tree
• Number Of Allocations
• Extra Bits
• Virtual Memory
• Time Complexity
• Hardness Distribution
• Hash Function
• succinct data structures
• dynamic data structures
• B-trees