2025/10/22 by William Kuszmaul, Kuszmaul, William, Jingxun Liang +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2510.19175
openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of n elements from a universe of size U, that achieves the optimal amortized expected time complexity of O(1 + log n / log log U), while achieving a nearly optimal space consumption of log \binomUn + n / 2^(log n)Ω(1) + polylog U bits in the regime where U = poly(n). This resolves an open question by Pibiri and Venturini as to whether a redundancy (a.k.a. space overhead) of o(n) bits is possible, and is the first dynamic solution to bypass the so-called tree-structure bottleneck, in which the bits needed to encode some dynamic tree structure are themselves enough to force a redundancy of \widetildeΩ(n) bits. Our main technical building block is a dynamic balanced binary search tree, which we call the compressed tabulation-weighted treap, that itself achieves a surprising time/space tradeoff. The tree supports polylog n-time operations and requires a static lookup table of size poly(n) + polylog U -- but, in exchange for these, the tree is able to achieve a remarkable space guarantee. Its total space redundancy is O(log U) bits. In fact, if the tree is given n and U for free, then the redundancy further drops to O(1) bits.