8 papers
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…
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…
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust…
Adversarial Robustness on Insertion-Deletion Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for in…
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…
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…