4 papers
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
We show how to implement a dynamic array with symbols from a fixed alphabet , while supporting -time queries and updates, and using a total space of $$ \log \bin…
Dynamic Dictionary with Subconstant Wasted Bits per Key
Tianxiao Li, Jingxun Liang, Huacheng Yu +1
Dictionaries have been one of the central questions in data structures. A dictionary data structure maintains a set of key-value pairs under insertions and deletions such that give…
Dynamic "Succincter"
Tianxiao Li, Jingxun Liang, Huacheng Yu +1
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…
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Tianxiao Li, Jingxun Liang, Huacheng Yu +1
A dictionary data structure maintains a set of at most keys from the universe under key insertions and deletions, such that given a query , it returns if i…