Optimal Bounds for Open Addressing Without Reordering
Martin Farach-Colton, Andrew Krapivin, William Kuszmaul
https://arxiv.org/abs/2501.02305
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 with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper ``Uniform Hashing is Optimal’’. All of our results come with matching lower bounds.
Undergraduate Upends a 40-Year-Old Data Science Conjecture
Tiny Pointers
Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini
https://arxiv.org/abs/2111.12800
This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional \( log n \) -bit pointers can be replaced with \( O(log n) \) -bit tiny pointers at the cost of only a constant-factor time overhead. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an element in an array filled to load factor , then the optimal tiny-pointer size is bits in the fixed-size case, and expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest.
Using tiny pointers, we revisit five classic data-structure problems: the data-retrieval problem, succinct dynamic binary search trees, space-efficient stable dictionaries, space-efficient dictionaries with variable-size keys, and the internal-memory stash problem. These are all well-studied problems, and in each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.
Du-Hwang Characteristic Area: Catch-22
A.O.Ivanov, A.A.Tuzhilin
https://arxiv.org/abs/1402.6079
The paper is devoted to description of two interconnected mistakes generated by the gap in the Du and Hwang approach to Gilbert-Pollack Steiner ratio conjecture.