4 citations · 8 across the 31 of their papers we have counts for
5 papers · 1 filter
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…
On the Optimal Time/Space Tradeoff for Hash Tables
Michael A. Bender, Martín Farach-Colton, John Kuszmaul +2
For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art h…
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once
Michael A. Bender, Alex Conway, Martín Farach-Colton +2
Despite being one of the oldest data structures in computer science, hash tables continue to be the focus of a great deal of both theoretical and empirical research. A central reas…
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul
First introduced in 1954, linear probing is one of the oldest data structures in computer science, and due to its unrivaled data locality, it continues to be one of the fastest has…