2 citations · 2 across the 8 of their papers we have counts for
4 papers · 2 filters
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…