PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Thresholds for Cuckoo Hashing via XORSAT

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink

arXiv:0912.0287v3cs.DS

TL;DR

Offline cuckoo hashing requires a tight load threshold separating high-probability success from failure. The paper derives this threshold by relating cuckoo hashing to random k-XORSAT, then extends the analysis to irregular choices and conjectures the multi-key-bucket case.

  • Problem

    The paper addresses the open question of determining tight success thresholds for offline cuckoo hashing with k ≥ 3 random choices per key.

  • Method

    The paper maps cuckoo-hashing instances to random hypergraphs and modulo-2 linear systems, then analyzes cores and irregular degree distributions.

  • Results

    For k > 2, c_k,2 is the threshold for k-ary cuckoo hashing, with success below it and failure above it with high probability.

  • Takeaways & Limitations

    The thresholds for one-key-per-bucket cuckoo hashing equal known random k-XORSAT thresholds, while irregular choices can be optimized and multi-key buckets remain conjectural.

  • Takeaways & Limitations

    For k > 2 and bucket capacity ℓ > 1, the appropriate cuckoo-hashing thresholds lack rigorous analysis and are supported by a conjecture and experimental evidence.

Abstract

from arXiv · show

We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k >= 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds alpha_k such that, as n goes to infinity, if n/m <= alpha for some alpha < alpha_k then a hash table can be constructed successfully with high probability, and if n/m >= alpha for some alpha > alpha_k a hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k > 2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem. We then extend these results to the setting where keys can have differing number of choices, and provide evidence in the form of an algorithm for a conjecture extending this result to cuckoo hash tables that store multiple keys in a bucket.

1 Introduction

The paper addresses the open problem of determining tight success thresholds for offline k-ary cuckoo hashing and connects them to random k-XORSAT thresholds. It also studies irregular choices and multi-key buckets.

  • Problem: The problem asks for a tight load threshold separating successful from unsuccessful offline cuckoo hashing with high probability.Each key has k ≥3 distinct randomly chosen buckets, and each bucket holds one key.
  • Main result: The paper shows that cuckoo-hashing thresholds correspond exactly to previously known random k-XORSAT thresholds.The connection provides thresholds for all k > 2.
  • Extensions: Irregular cuckoo hashing allows each key’s number of choices to be a random variable rather than a fixed constant.The paper optimizes such schemes for a specified average number of choices.
  • Extensions: With an average of 3.5 choices, the optimal irregular scheme gives half the keys 3 choices and half 4 choices.This is the natural two-point distribution around the average.
  • Extensions: For buckets holding multiple keys, the paper conjectures threshold behavior and gives an algorithm whose experiments approach the conjectured thresholds.This extension is presented as evidence rather than a rigorous result.
  • Organization: The paper reviews random-hypergraph cores, proves threshold equality, extends thresholds to real k > 2, and evaluates a simple placement algorithm.The sections develop the core analysis, equality proof, non-integer choices, and experimental algorithmic evidence.

2 Technical background on cores

The technical background analyzes ℓ-cores of random k-uniform hypergraphs using iterative peeling and local tree approximations. Core emergence and its edge density provide the threshold quantities later used for cuckoo hashing.

  • Random hypergraphs: For n = cm with fixed c, the random hypergraph model uses n labeled k-edge hyperedges selected independently with repetition.The analysis assumes fixed k, sufficiently large m, and constant edge density c.
  • Core definition: An ℓ-core is the largest induced sub-hypergraph with minimum degree at least ℓ, obtained by repeatedly peeling lower-degree nodes.Conditioned on its size, the remaining core is uniform subject to the degree constraint.
  • Peeling analysis: A node’s fate after h peeling rounds is determined by its h-neighborhood, which is typically a low-degree hypertree when n is linear in m.The peeling decision can therefore be analyzed recursively from the leaves toward the root.
  • Peeling analysis: The deletion probabilities form a monotone bounded sequence, so their limit is well-defined and is characterized as the smallest nonnegative fixed-point solution.Poisson approximations describe the numbers of surviving child hyperedges.
  • Core thresholds: The threshold c*_k,ℓ separates an empty ℓ-core from an ℓ-core of linear size with high probability.Below the threshold the core is empty; above it, a linear-size core survives.
  • Core thresholds: Above c*_k,ℓ, the core contains approximately Pr[Po(β(c)) ≥ℓ] · m nodes and (Pr[Po(β(c)) ≥ℓ−1])^k · n hyperedges.These concentrations determine the core’s edge density.
  • Connection to hashing: The values c_k,ℓ are used to show c_k,2 is the threshold for k-ary cuckoo hashing and to conjecture c_k,ℓ+1 for bucket capacity ℓ.Numerical values are tabulated for ℓ = 2, …, 7 and k = 2, …, 7.

3 Equality of thresholds for random k-XORSAT and k-ary cuckoo hashing

The paper relates random k-XORSAT to cuckoo hashing through their shared hypergraph structure. It proves that for k > 2, both problems have the same threshold c_k,2.

  • Random k-XORSAT: Random k-XORSAT is a system of modulo-2 linear equations, each involving k variables and a randomly chosen right-hand side.The equivalent clause formulation uses XOR satisfaction.
  • Random k-XORSAT: Peeling variables occurring once preserves satisfiability and leaves a random formula whose variables all occur at least twice.The residual formula corresponds to the 2-core of its associated hypergraph.
  • XORSAT threshold: The residual XORSAT formula is likely satisfiable when its edge density is below 1 and likely unsatisfiable when the density exceeds 1.This criterion yields the satisfiability threshold c_k,2.
  • Cuckoo-hashing threshold: For k > 2, c_k,2 is the threshold for k-ary cuckoo hashing: above it hashing fails with high probability, while below it hashing succeeds with high probability.The theorem considers fixed c = n/m as m tends to infinity.
  • Cuckoo-hashing threshold: Above the threshold, the 2-core has more hyperedges than buckets, so the corresponding keys cannot be placed injectively.The hyperedges represent keys and the core nodes represent their available buckets.
  • Cuckoo-hashing threshold: Below the threshold, random right-hand sides are satisfiable with high probability, implying linearly independent key-bucket rows and a successful key-to-bucket permutation.A nonzero determinant yields a permutation assigning keys to distinct buckets.

4 Non-integer choices

The paper extends cuckoo-hashing thresholds to non-integral average choices using irregular degree distributions, showing optimal distributions concentrate choices on adjacent integers and identifying the corresponding threshold.

  • Optimal degree distributions: For fixed expected choices, an optimal distribution concentrates each key’s choices on ⌊κx⌋ and ⌊κx⌋ + 1.When κx is integral, fixing kx = κx is optimal; in the equal-average case, the support is ⌊κ∗⌋ and ⌊κ∗⌋ + 1.
  • Generalization to non-integral choices: Non-integral cuckoo hashing assigns each key a random number of choices, represented by degree distributions with average κ∗.The analysis models varying hyperedge degrees through a generating function and Poisson asymptotics.
  • Threshold characterization: The threshold cκ∗,2 is determined by the point where the corresponding 2-core has edge density 1, matching the solvability condition for the associated XORSAT problem.This characterization applies to arbitrary degree distributions under the stated restrictions, while optimal thresholds use the adjacent-integer distributions.
  • Threshold behavior: For c > cκ∗,2, cuckoo hashing fails with high probability for any choice distribution with mean κ∗.For c < cκ∗,2, it succeeds with high probability under the specified adjacent-integer distribution.
  • Numerical thresholds: For κ∗ ≤ 2.25, the numerically determined threshold appears to be c = 0.5/(3 − κ∗).The paper states that mixing 2- and 3-choice keys can increase space utilization by 33% relative to using 2 hash functions per key, with the same asymptotic memory.

5 Algorithm for computing a placement

The paper presents a generalized selfless algorithm for placing keys by orienting hyperedges under bucket-capacity constraints, and uses experiments to assess its proximity to theoretical thresholds and a multi-key conjecture.

  • Placement algorithm: The generalized selfless algorithm finds placements by orienting each hyperedge toward an associated bucket while respecting maximum indegree constraints.It handles uniform and varying-degree hypergraphs and is adapted from an algorithm for standard graphs.
  • Bucket size 1: For bucket size 1, the algorithm prioritizes nodes and directs minimum-weight incident hyperedges, returning failure when the indegree constraint cannot be maintained.Weights reflect the number of unsaturated nodes in an unoriented hyperedge, while node priorities sum inverse incident weights.
  • Empirical performance: Experiments on hypergraphs with 10^5 and 10^6 nodes show failure rates near the theoretical thresholds c_k,2 for k = 3, 4, 5.The reported tests evaluate the generalized selfless algorithm around the corresponding threshold values.
  • Larger bucket capacities: For bucket size ℓ > 1, the paper conjectures a threshold at c_k,ℓ+1, where the (ℓ + 1)-core first has edge density greater than ℓ.The generalized algorithm orients hyperedges so that each node receives at most ℓ directed hyperedges.
  • Evidence for the conjecture: Experiments with the capacity-ℓ algorithm show a failure-rate transition from 0 to 1 close to the conjectured threshold values.These experiments are presented as evidence for Conjecture 1 rather than as a rigorous threshold analysis.

6 Conclusion

The paper finds tight thresholds for single-key-per-bucket cuckoo hashing by identifying them with previously known k-XORSAT thresholds. It also extends the result to irregular choice distributions and conjectures thresholds for larger bucket sizes.

  • The tight thresholds for cuckoo hashing with one key per bucket equal the previously studied thresholds for random k-XORSAT.
  • Optimality of degree distribution: The analysis considers optimal degree distributions by showing that distributions with separated support values cannot maximize the relevant success probability.

B Performance results for the generalized selfless algorithm

Experiments evaluate the generalized selfless algorithm near theoretical thresholds for k = 3, 4, and 5. The algorithm performs close to the thresholds, with increasingly sharp success-to-failure transitions as system size and edge size grow.

  • Experiments with 10^5 and 10^6 nodes measure failure rates around c_k,2 for k = 3, 4, and 5.
  • The generalized selfless algorithm constructs placements at edge densities quite close to the calculated thresholds.
  • As m and k grow, the transition from total success to total failure becomes sharper, although the algorithm can fail on hypergraphs that admit a matching.
  • Theoretical thresholds are approximately 0.91794 for k = 3, 0.97677 for k = 4, and 0.99244 for k = 5.
  • Differences between generalized selfless and perfect-matching failure rates become very small as m grows.
  • For bucket size ℓ greater than 1, the generalized algorithm shows similar behavior, illustrated by the conjectured threshold c_3,3 ≈1.97640.

C Proof of the threshold for k-XORSAT

The proof establishes the k-XORSAT threshold by reducing random systems to their 2-cores and analyzing satisfiability on the resulting core. Below and above the core-density threshold, satisfiability probabilities behave in opposite ways.

  • The proof combines core results, a concentration lemma, and Friedgut’s Theorem to establish the k-XORSAT threshold.
  • The threshold function satisfies probability tending to 1 below c_k(m)(1−ε) and 0 above c_k(m)(1+ε).
  • Below c_k,2, the reduced 2-core has fewer equations than variables with high probability, and the system is satisfiable with probability bounded away from zero.
  • Above c_k,2, the reduced 2-core has more equations than variables with high probability, making satisfiability probability exponentially small.
  • The proof analyzes the number of solutions through combinatorial counting, coefficient extraction, and a unique maximum of the function ψ.

C.2 Proof of Lemma 4

The proof of Lemma 4 bounds combinatorial contributions to the solution count using entropy expressions and saddle-point-style maximization. The auxiliary function ψ has a unique global maximum at the symmetric point.

  • The proof bounds N(w,l) using coefficient estimates, Stirling’s formula, and asymptotic comparisons of combinatorial terms.
  • The analysis represents degree counts with independent Poisson variables conditioned to be at least 2.

C.3 Proof of Lemma 5, outline

The proof reduces the maximization of ψ to a sequence of parameter transformations and stationarity arguments. It establishes that the unique global maximum occurs at (ω, λ) = (1/2, 1/2), with value 2^(1−γ).

  • Candidate maximizer: For (ω, λ) = (1/2, 1/2), the defining equations have the unique solution a = b = s and c = 1.At this point, ψ(1/2, 1/2) = (1 − γ) log 2, equivalently 2^(1−γ).
  • Interior maximum: Convexity and boundary asymptotics imply that any global maximum of ψ lies at an interior stationary point.The proof then shows that (1/2, 1/2) is the only such point.
  • Parameter reduction: The proof transforms Ψ by optimizing over ω, reparameterizing λ through c, and rescaling a and b to reduce the problem to fewer free parameters.It first restricts to λ ≤ 1/2, then defines Ψ1, Ψ2, and Ψ3 through these reductions.
  • Global maximization: The remaining one-dimensional analysis shows that c = 1 is the global maximum of Ψ4(c) on [0, 1].The auxiliary function F_s is convex, so the only additional solution in the interior is a local minimum.
  • Conclusion: Theorem 4 concludes that ψ has a unique global maximum at (1/2, 1/2), where ψ(1/2, 1/2) = 2^(1−γ).The argument restricts to λ ≤ 1/2 using the symmetry inequality for λ > 1/2 and applies Proposition 5 to P = λ/(1 − λ).

Proof of (65)

The proof of (65) establishes bounds on Γ by partitioning the range of P = ac and controlling representative parameter pairs. Monotonicity in s and auxiliary inequalities extend these bounds across the required ranges.

  • Anchor bounds: Γ(a, c, s) < B for a constant B < 2 at four selected parameter pairs under explicit lower bounds on s.The pairs include a = 1 − 1/Q with c = 1/Q or 11/20, and a = 1/2 with c = 1/Q or 1/(2Q).
  • Range decomposition: The argument partitions all P = ac in [0, 1] into ranges covered by Lemmas 10–13.The ranges are controlled using boundary values, selected parameter pairs, and the regions near P = 0 and P = 1.
  • Monotonicity checks: 1.9971... bounds the relevant Γ expression at s = 5 for (a, c) = (1 − 1/Q, 11/20).The corresponding limit as s → ∞ is 1.9505....
  • Monotonicity checks: Γ1(a, s) decreases in s, while the corresponding Γ2 expression increases in s for the cases used in the proof.These monotonicity statements allow finite-s inequalities to imply the required bounds over the stated ranges.
  • Monotonicity checks: The auxiliary limits are 1.8718... for Γ2(1/Q, 1/2, s) and 1.7563... for Γ2(1/2, 1/(2Q), s) as s → ∞.Both values are below 2, supporting the selected-pair bounds.

D.4 Proof of Lemma 12

Lemma 12 bounds Γ in the region near ac = 0 by selecting c as a function of a and proving monotonic decrease. The bound is at most 2, with equality only at the boundary a = 0.

  • Statement: For s ≥ 4.2, Γ(A, c, s) ≤ 2 for 0 ≤ c ≤ 1/(2Q), with equality only for c = 0.Here A is chosen as A(c, s) = c · Q.
  • Reparameterization: Setting C(a, s) = a/Q converts the lemma into proving Γ(a, C, s) ≤ 2 for 0 ≤ a ≤ 1/2.The equality case becomes a = 0 because C(0, s) = 0 and Γ(0, 0, s) = 2.
  • Monotonicity: The proof shows that Γ(a, C, s) is strictly decreasing for 0 < a ≤ 1/2.Two inequalities for the additive terms imply this monotonicity.
  • Conclusion: The endpoint checks and monotonicity establish the bound throughout the region near ac = 0.The numerical check at s = 4.2 supplies the base case, and the derivative argument extends it to all s ≥ 4.2.

D.5 Proof of Lemma 13

Lemma 13 controls the region near ac = 1 by choosing A as an affine function of c and proving Γ increases toward its endpoint. Equality occurs only at c = 1.

  • Statement: For s ≥ 6, Γ(A, c, s) ≤ 2 for 2/5 ≤ c ≤ 1, with equality only for c = 1.The parameter choice is A(c, s) = (85/(100Q))c + 1 − 85/(100Q).
  • Conclusion: The endpoint value and strict increase prove the upper bound and its equality condition for the entire interval.The argument applies for s ≥ 6, using the stated auxiliary inequalities.
  • Endpoint strategy: The proof defines A(c, s) so that A(1, s) = 1 and Γ(1, 1, s) = 2.It then reduces the result to showing Γ(A, c, s) is strictly increasing for 2/5 ≤ c < 1.
  • Monotonicity: The derivative inequalities imply that Γ(A, c, s) is increasing over the interval 2/5 ≤ c < 1.Concavity of PPLUS(c, Q − 1) is used to extend the inequality from c = 2/5 to the full interval.
Loading 0912.0287v3…