From the 1 of 8 linked papers with an AI index.
8 papers
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
The dynamic dictionary is a fundamental data structure that maintains a set of size (we assume ), supporting insertions, deletions and membership q…
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood
Yang Hu, William Kuszmaul, Jingxun Liang +3
The paper studies a smoothed version of quadratic probing for hash tables, comparing Robin Hood and anti‑Robin Hood insertion orders and showing that anti‑Robin Hood achieves logar…
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…
Optimal Static Fully Indexable Dictionaries
Jingxun Liang, Renfei Zhou
Fully indexable dictionaries (FID) store sets of integer keys while supporting rank/select queries. They serve as basic building blocks in many succinct data structures. Despite th…