Dynamic "Succincter"
Preprint
Abstract
Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work "succincter" by Patrascu 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). It supports updates and queries in $O(\log n/\log\log n)$ time, and when the array has $m$ ones, the data structure occupies \[ \log\binom{n}{m} + O(n/2^{\log^{0.199}n}) \] bits. Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks. 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(n \cdot \text{poly}\log\log n/\log^2 n)$ bits of redundancy.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- In-place initializable arraysTheoretical Computer Science, 2022
- Fully Functional Static and Dynamic Succinct TreesACM Transactions on Algorithms, 2014
- Optimal Dynamic Sequence RepresentationsSIAM Journal on Computing, 2014
- Rank/select on dynamic compressed sequences and applicationsTheoretical Computer Science, 2009
- Dynamic entropy-compressed sequences and full-text indexesACM Transactions on Algorithms, 2008
- Optimal lower bounds for rank and select indexesTheoretical Computer Science, 2007
- Space Efficient Suffix TreesJournal of Algorithms, 2001
- Low Redundancy in Static Dictionaries with Constant Query TimeSIAM Journal on Computing, 2001