34 citations · 131 across the 30 of their papers we have counts for
30 papers · 1 filter
An Associativity Threshold Phenomenon in Set-Associative Caches
Michael A. Bender, Rathish Das, Martín Farach-Colton +1
In an -way set-associative cache, the cache is partitioned into disjoint sets of size , and each item can only be cached in one set, typically selected via a hash function. S…
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
Prashant Pandey, Michael A. Bender, Alex Conway +4
Modern hash table designs strive to minimize space while maximizing speed. The most important factor in speed is the number of cache lines accessed during updates and queries. This…
Contention Resolution for Coded Radio Networks
Michael A. Bender, Seth Gilbert, Fabian Kuhn +2
Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a w…
GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
David Tench, Evan West, Victor Zhang +6
Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more…
Online List Labeling: Breaking the Barrier
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing se…
Tiny Pointers
Michael A. Bender, Alex Conway, Martín Farach-Colton +2
This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional -bit pointers can be replaced with -bit ti…