4 citations · 8 across the 31 of their papers we have counts for
7 papers · 1 filter
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 Non-Oblivious Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
A hash table is said to be open-addressed (or non-obliviously open-addressed) if it stores elements (and free slots) in an array with no additional metadata. Intuitively, open-addr…
Optimal Bounds for Open Addressing Without Reordering
Martin Farach-Colton, Andrew Krapivin, William Kuszmaul
In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved…
Tight Analyses of Ordered and Unordered Linear Probing
Mark Braverman, William Kuszmaul
Linear-probing hash tables have been classically believed to support insertions in time , where is the load factor of the hash table. Recent work by Bender, Kuszm…
Efficient -ary Cuckoo Hashing at High Load Factors by Bubbling Up
William Kuszmaul, Michael Mitzenmacher
A -ary cuckoo hash table is an open-addressed hash table that stores each key in one of random positions . In the offline setting, where…