4 citations · 7 across the 14 of their papers we have counts for
4 papers · 1 filter
Lower Bounds for Linear Hashing via Arithmetic Kakeya
Ainesh Bakshi, Alex Conway, Hanna Komlós +2
Affine modular linear hashing is one of the simplest classical hash families. For a prime , the hash function is obtained by choosing uniformly from and…
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…
Succinct and Fast Tiny Pointer Hash Tables
Xilin Tang, Yuqi Mai, William Kuszmaul +1
Hash tables sit on the critical path of many systems, yet modern designs still force a trade-off between fast operations and high memory overhead. We revisit this trade-off and pre…
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…