2 citations · 2 across the 8 of their papers we have counts for
10 papers · 1 filter
The Power of Two-Choice Linear Probing
Amir Azarmehr, Michael A. Bender, William Kuszmaul +1
This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected…
Tight Bounds for Memory Allocation With and Without Request Fragmentation
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known…
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
History-Independent Load Balancing
Michael A. Bender, William Kuszmaul, Elaine Shi +1
We give a (strongly) history-independent two-choice balls-and-bins algorithm on bins that supports both insertions and deletions on a set of up to balls, while guaranteeing…
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…
Layered List Labeling
Michael A. Bender, Alex Conway, Martin Farach-Colton +2
The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and…
What Does Dynamic Optimality Mean in External Memory?
Michael A. Bender, Martín Farach-Colton, William Kuszmaul
In this paper, we revisit the question of how the dynamic optimality of search trees should be defined in external memory. A defining characteristic of external-memory data structu…