12 papers · 1 filter
Quadratic Probing Insertions Are Time
Yang Hu, William Kuszmaul, Jingxun Liang +3
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectur…
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
Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees rema…
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…
Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, Huacheng Yu +2
In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U…
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…
On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching
Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu +2
Ranking and Balance are arguably the two most important algorithms in the online matching literature. They achieve the same optimal competitive ratio of for the integral ve…