2 citations · 2 across the 7 of their papers we have counts for
6 papers · 1 filter
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…
Fast Concurrent Primitives Despite Contention
Michael A. Bender, Guy E. Blelloch, Martin Farach-Colton +4
We study the problem of constructing concurrent objects in a setting where processes run in parallel and interact through a shared memory that is subject to write contention. O…
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…
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…
Efficiently Constructing Sparse Navigable Graphs
Alex Conway, Laxman Dhulipala, Martin Farach-Colton +6
Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to…
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…