4 papers
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…