4 papers · 1 filter
Time To Replace Your Filter: How Maplets Simplify System Design
Michael A. Bender, Alex Conway, Martín Farach-Colton +2
Filters such as Bloom, quotient, and cuckoo filters are fundamental building blocks providing space-efficient approximate set membership testing. However, many applications need to…
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…
Tight Bounds for Classical Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to , while also supporting expected-time queri…
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, Martín Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…