4 citations · 9 across the 7 of their papers we have counts for
7 papers
Adaptive Quotient Filters
Richard Wen, Hunter McCoy, David Tench +6
Adaptive filters, such as telescoping and adaptive cuckoo filters, update their representation upon detecting a false positive to avoid repeating the same error in the future. Adap…
Optimal Uncoordinated Unique IDs
Peter C. Dillinger, Martín Farach-Colton, Guido Tagliavini +1
In the Uncoordinated Unique Identifiers Problem (UUIDP) there are independent instances of an algorithm that generates IDs from a universe , and…
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…
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…
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…
Star Routing: Between Vehicle Routing and Vertex Cover
Diego Delle Donne, Guido Tagliavini
We consider an optimization problem posed by an actual newspaper company, which consists of computing a minimum length route for a delivery truck, such that the driver only stops a…