5 papers
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
William Kuszmaul, Jingxun Liang, Renfei Zhou
We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of elements from a universe of size , that achieves the optimal amortize…
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, Jingxun Liang +3
In the static retrieval problem, a data structure must answer retrieval queries mapping a set of keys in a universe to -bit values. Information-theoretically, retrieva…
Fingerprint Filters Are Optimal
William Kuszmaul, Jingxun Liang, Renfei Zhou
Dynamic filters are data structures supporting approximate membership queries to a dynamic set of keys, allowing a small false-positive error rate , under inse…
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…