Random linear hashing behaves like fully random hashing in bin loads
Linear Hashing Is Poissonesque
Data Structures and AlgorithmsComputational ComplexityInformation Theory
Summary
When assigning many items into many bins randomly, the way items spread out can often be approximated by a particular mathematical distribution called a Poisson distribution. This paper shows that even when items are assigned using a specific type of random linear function instead of complete randomness, the distribution of how full the bins get still behaves very similarly to the ideal case. The authors prove this by comparing average and maximum bin loads and show that the linear method nearly matches fully random assignments. This finding improves understanding of how certain hashing methods work and how reliable their distribution properties are.
What this means in practice
- •For distributed system engineers: Design hash-based load balancing mechanisms that use random linear functions with nearly the same load distribution guarantees as fully random hashes.
- •For database architects: Improve hash indexing schemes by employing random linear maps to achieve predictable bin load distributions and concentration bounds akin to full randomness.
A theory result. No direct application yet.
Authors
Vinayak M. Kumar
Abstract
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th largest value among $n$ independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when $n$ balls are hashed into $n$ bins by a random $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/ρ)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$ρ$ subset of bins will contain a $(1\pm o(1) )ρ$-fraction of the balls. We show that this remains the case if the $m$ balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load $m/n \pm O(\sqrt{(m/n)\log n})$ with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.