betaFeedback

WorksComputer Science

Exact Failure Probabilities for d-Choice Cuckoo Hashing

Abstract

In d-choice cuckoo hashing, each of n items must be placed in one of its d candidate slots in a table of M slots, and every slot holds at most one item. We give a polynomial-time dynamic programming algorithm to compute the exact probability that no valid placement exists. Our method also handles the variant with separate tables.

Introduction

Cuckoo hashing has been used in a wide range of applications, including key-value stores [6], network switches [20], approximate membership filters [7], page tables [18], and cryptographic protocols [11, 17, 1].

In the basic one-table variant of dd-choice cuckoo hashing, each of nn items must be placed in one of its dd candidate slots in a table of MM slots, and every slot holds at most one item [15, 10]. We study its failure probability, denoted pfail(n,M,d)p_{\mathrm{fail}}(n, M, d), that the candidate slots of the items admit no valid placement.

Previous work has established load thresholds for dd-choice cuckoo hashing [4, 8, 9], and upper bounds on its failure probability [10, 19, 16]. The exact failure probability has also been obtained for d=2d = 2 [12, 13, 14 DK12], but has remained open for d≥3d \ge3 [13 §1.5.3], [1].

Our results. We compute the exact value of pfail(n,M,d)p_{\mathrm{fail}}(n, M, d) for any nn, MM, and dd in O(n2log⁡n)O(n^2 \log n) time. We use Beniamini’s coefficient formula for perfect matching [2] to express the number of failing outcomes as a sum of exponentially many terms. We then compute this sum using dynamic programming. Our method also extends to the variant with dd separate tables (possibly of unequal sizes), where it computes pfail(n,m,d)p_{\mathrm{fail}}(n, m, d) in O(nd+2)O(n^{d+2}) time. The implementations of our algorithms are available at https://github.com/zcy05331/Cuckoo-Failure.

Model and preliminaries

Model

There are nn items labeled [n]={1,…,n}[n] = \{1,\ldots,n\}. In the one-table variant, there are MM slots labeled [M]={1,…,M}[M] = \{1,\ldots,M\} with $1 \le d < n < M$. Each item ii independently draws a uniform dd-element candidate set Γ(i)⊆[M]\Gamma(i) \subseteq[M], and must be placed in one of the dd slots. Each item thus has Q=(Md)Q = \binom{M}{d} possible candidate sets.

An outcome ω=(Γ(1),…,Γ(n))\omega= (\Gamma(1),\ldots,\Gamma(n)) lists the candidate sets of all items, and the QnQ^n outcomes are equally likely. An outcome ω\omega can be captured by a candidate graph GωG_\omega: a bipartite graph with the items on one side, the slots on the other, and an edge (i,j)(i,j) for each j∈Γ(i)j \in\Gamma(i). A placement of the items is a matching of GωG_\omega that covers every item. An outcome ω\omega leads to a failure if GωG_\omega has no such matching. Let NbadN_{\mathrm{bad}} be the number of failing outcomes. We have pfail=Nbad/Qnp_{\mathrm{fail}} = N_{\mathrm{bad}}/Q^n.

We will later consider two variants: independent draws with replacement (§ 3.4) and separate tables (§ 4).

Beniamini's coefficient formula

Beniamini’s expansion. Let GG be a bipartite graph with MM left vertices and MM right vertices, and let KM,MK_{M,M} denote the complete bipartite graph on the same vertex set. For a left vertex ii and a right vertex jj, let xij=1x_{ij} = 1 if the edge (i,j)(i,j) is missing from GG and xij=0x_{ij} = 0 otherwise; we call x=(xij)i,j∈[M]x = (x_{ij})_{i,j\in[M]} the missing-edge indicators of GG. Beniamini and Nisan [3] analyze bipartite matching with a multilinear polynomial BPMM∗(x)\mathrm{BPM}^{*}_{M}(x). BPMM∗(x)\mathrm{BPM}^{*}_{M}(x) is 1 if GG has no perfect matching and 0 otherwise. They show that this indicator polynomial has integer coefficients as follows [3, 2]:

BPMM∗(x)=∑H⊆KM,MaH∗xH,xH=∏(i,j)∈E(H)xij.(1)\mathrm{BPM}^{*}_{M}(x) = \sum_{H\subseteq K_{M,M}} a^{*}_{H}x^{H}, \qquad x^{H} = \prod_{(i,j)\in E(H)} x_{ij}. \tag*{(1)}

In the above, HH ranges over all bipartite graphs on the same 2M2M vertices. Observe that xH=1x^{H} = 1 if every edge of HH is missing from GG and 0 otherwise. Beniamini [2] determined the coefficients aH∗a^{*}_{H}. To state his formula, we define totally ordered graphs.

Definition 2.1 (Totally ordered graphs [3, 2]). Let HH be a bipartite graph and TH(i)={j:(i,j)∈E(H)}T_H(i) = \{j : (i,j) \in E(H)\} be the neighborhood of its ii-th left vertex. HH is totally ordered if the neighborhoods of its left vertices are totally ordered by inclusion: for all left vertices ii and i′i', either TH(i)⊆TH(i′)T_H(i) \subseteq T_H(i') or TH(i′)⊆TH(i)T_H(i') \subseteq T_H(i).

For a totally ordered graph HH, order the distinct neighborhoods of the left vertices as T1⊊T2⊊⋯⊊TLT_1 \subsetneq T_2 \subsetneq\cdots\subsetneq T_L. The left vertices whose neighborhood is TiT_i form block ii. Let bi=∣Ti∣b_i = |T_i| be their degree, and let kik_i be the number of left vertices in blocks 1,…,i1,\ldots,i, with k0=0k_0 = 0:

0≤b1<⋯<bL≤M,0=k0<k1<⋯<kL=M.(2)0 \le b_1 < \cdots< b_L \le M, \qquad0 = k_0 < k_1 < \cdots< k_L = M. \tag*{(2)}
A totally ordered graph H with M = 7 vertices on each side

Figure 1. A totally ordered graph HH with M=7M=7 vertices on each side. Rows represent left vertices, columns represent right vertices, and a shaded cell is an edge of HH. The representing sequence is (ki,bi)=(2,0),(4,3),(7,5)(k_i,b_i)=(2,0),(4,3),(7,5). It indicates that two left vertices have no neighbors, two left vertices have (the same) three right neighbors, and three left vertices have (the same) five right neighbors.

Block ii thus consists of ki−ki−1k_i-k_{i-1} left vertices, each of degree bib_i. (k,b)=(ki,bi)i<L(\mathbf{k},\mathbf{b})=(k_i,b_i)_{i<L} is called the representing sequence of HH. Figure 1 gives an example. Throughout, we define (ab)=0\binom{a}{b}=0 unless a,ba,b are integers with 0≤b≤a0\le b\le a. Empty products and 000^0 equal one.

Theorem 2.2 (Beniamini [2 Theorem 2]). If H⊆KM,MH\subseteq K_{M,M} is not totally ordered, then aH∗=0a_H^*=0. If HH is totally ordered with representing sequence (2), then

aH∗=(M−kL−1−1M−bL)∏i=1L−1ϕ(bi+1−ki−1,bi−ki−1,ki−ki−1)(3)a_H^*=\binom{M-k_{L-1}-1}{M-b_L}\prod_{i=1}^{L-1}\phi(b_{i+1}-k_{i-1},b_i-k_{i-1},k_i-k_{i-1}) \tag*{(3)}

where

ϕ(a,b,r)={(a−1r),b≤0,−(a−b−1r−b)(r−1b−1),b>0.(4)\phi(a,b,r)= \begin{cases} \binom{a-1}{r}, & b\le0,\\ -\binom{a-b-1}{r-b}\binom{r-1}{b-1}, & b>0. \end{cases} \tag*{(4)}

The coefficient in (3) depends on HH only through its representing sequence. We write it as α(k,b)\alpha(\mathbf{k},\mathbf{b}). Graphs that differ only by permutations of the two vertex sets have the same coefficient.

Dummy items. A candidate graph GωG_\omega has nn item vertices and MM slot vertices. Since Beniamini’s formula (1) requires an equal number of left vertices and right vertices, we add M−nM-n dummy items that can be placed in any slot. The resulting graph G^ω\widehat{G}_\omega has MM vertices on each side, and it has a perfect matching if and only if GωG_\omega has a matching that covers every left vertex.

Evaluation by dynamic programming

Counting failing outcomes

By (1), the number of failing outcomes is

Nbad=∑ωBPM⁡M∗(x(ω))=∑H⊆KM,MaH∗∑ωxH(ω)(5)N_{\mathrm{bad}}=\sum_{\omega}\operatorname{BPM}^{*}_{M}(x(\omega))=\sum_{H\subseteq K_{M,M}}a_H^*\sum_{\omega}x^H(\omega) \tag*{(5)}

where ω\omega ranges over the QnQ^n outcomes and x(ω)x(\omega) are the missing-edge indicators of G^ω\widehat{G}_{\omega}.

By Theorem 2.2, only totally ordered graphs can have aH∗≠0a_H^* \ne0. If HH contains an edge incident to a dummy item, that edge is present in G^ω\widehat{G}_{\omega} for every outcome, so xH(ω)=0x^H(\omega)=0. Thus, only totally ordered graphs in which every dummy item is isolated contribute to (5). Fix such a graph HH. The monomial xH(ω)x^H(\omega) equals 1 if and only if every item ii avoids its neighborhood TH(i)T_H(i), that is, Γ(i)∩TH(i)=∅\Gamma(i) \cap T_H(i)=\varnothing. We call TH(i)T_H(i) the forbidden set of item ii. If this set has size bb, the number of candidate sets that avoid it is

h(b)=(M−bd).(6)h(b)=\binom{M-b}{d}. \tag*{(6)}

The candidate sets of the nn real items can be chosen independently, so

∑ωxH(ω)=∏i=1nh(∣TH(i)∣).(7)\sum_{\omega}x^H(\omega)=\prod_{i=1}^{n}h(\lvert T_H(i)\rvert). \tag*{(7)}

Substituting into (5) gives

Nbad=∑HaH∗∏i=1nh(∣TH(i)∣),(8)N_{\mathrm{bad}}=\sum_H a_H^*\prod_{i=1}^{n}h(\lvert T_H(i)\rvert), \tag*{(8)}

where HH ranges over the totally ordered graphs in which every dummy item is isolated.

Grouping by representing sequences. Consider a graph HH that contributes to (8). Let (k,b)(\mathbf{k},\mathbf{b}) be its representing sequence. Its dummy items are isolated, so they have degree 0 and lie in the first block. Hence b1=0b_1=0 and k1≥zk_1\ge z, where z=M−n>0z=M-n>0 is the number of dummy items.

Let u1=k1−zu_1=k_1-z and ui=ki−ki−1u_i=k_i-k_{i-1} for 2≤i≤L2\le i\le L. Then uiu_i is the number of real items in block ii, and ∑iui=n\sum_i u_i=n. The term associated with HH in (8) can be rewritten as

a(k,b)∏ih(bi)uia(\mathbf{k},\mathbf{b})\prod_i h(b_i)^{u_i}

because every item of block ii has a forbidden set of size bib_i.

The number of graphs with a given representing sequence can be computed as follows. The nn real items are distributed among the blocks in n!/∏iui!n!/\prod_i u_i! ways. The nested sets T1⊊⋯⊊TLT_1\subsetneq\cdots\subsetneq T_L are chosen in (Mb1)∏i=1L−1(M−bibi+1−bi)\binom{M}{b_1}\prod_{i=1}^{L-1}\binom{M-b_i}{b_{i+1}-b_i} ways. Since b1=0b_1=0, the factor (Mb1)=1\binom{M}{b_1}=1 can be omitted. Let SL(n,M)S_L(n,M) be the set of representing sequences with LL blocks with b1=0b_1=0 and k1≥zk_1\ge z. We have

Nbad(n,M,d)=∑L=1M ∑(k,b)∈SL(n,M)a(k,b)n!∏i=1Lui!∏i=1L−1(M−bibi+1−bi)∏i=1Lh(bi)ui.(9)N_{\mathrm{bad}}(n,M,d)=\sum_{L=1}^{M}\ \sum_{(\mathbf{k},\mathbf{b})\in S_L(n,M)} a(\mathbf{k},\mathbf{b}) \frac{n!}{\prod_{i=1}^{L}u_i!} \prod_{i=1}^{L-1}\binom{M-b_i}{b_{i+1}-b_i} \prod_{i=1}^{L}h(b_i)^{u_i}. \tag*{(9)}

Direct evaluation would have to sum exponentially many nonzero representing sequences. We compute this sum with dynamic programming.

The forward recurrence

Blockwise factorization of each summand. For each representing sequence, we first express its contribution to (9) as a product of blockwise factors. The coefficient a(k,b)a(\mathbf{k},\mathbf{b}) already has this form according to (3). Each block i<Li < L contributes ϕ(bi+1−ki−1,bi−ki−1,ki−ki−1)\phi(b_{i+1} - k_{i-1}, b_i - k_{i-1}, k_i - k_{i-1}), and the last block contributes

(M−kL−1−1M−bL).\binom{M-k_{L-1}-1}{M-b_L}.

The (M−bibi+1−bi)\binom{M-b_i}{b_{i+1}-b_i} term belongs to block ii by definition. So does the h(bi)uih(b_i)^{u_i} term. The multinomial coefficient can also be decomposed to individual blocks:

n!∏i=1Lui!=∏i=1L(n−∑j<iujui),(10)\frac{n!}{\prod_{i=1}^{L}u_i!}=\prod_{i=1}^{L}\binom{n-\sum_{j<i}u_j}{u_i}, \tag*{(10)}

where (n−∑j<iujui)\binom{n-\sum_{j<i}u_j}{u_i} chooses the uiu_i items of block ii among the items not yet placed.

For a nonfinal block i<Li < L, we can think of (ki−1,bi)(k_{i-1},b_i) as the boundary at its start and (ki,bi+1)(k_i,b_{i+1}) as the boundary at its end. Let ν(ℓ)=max⁡{0,ℓ−z}\nu(\ell)=\max\{0,\ell-z\} be the number of real items among the first ℓ\ell left vertices. The factors associated with a nonfinal block with boundaries (ℓ,b)(\ell,b) and (r,c)(r,c) are

τ(ℓ,b;r,c)=ϕ(c−ℓ,b−ℓ,r−ℓ)(M−bc−b)(n−ν(ℓ)u)h(b)u,u=r−max⁡{ℓ,z}.(11)\tau(\ell,b;r,c)=\phi(c-\ell,b-\ell,r-\ell)\binom{M-b}{c-b}\binom{n-\nu(\ell)}{u}h(b)^u,\qquad u=r-\max\{\ell,z\}. \tag*{(11)}

For a fixed representing sequence, the corresponding summand in (9) can now be written as

∏i=1L−1τ(ki−1,bi;ki,bi+1)⋅(M−kL−1−1M−bL)h(bL)uL,(12)\prod_{i=1}^{L-1}\tau(k_{i-1},b_i;k_i,b_{i+1})\cdot\binom{M-k_{L-1}-1}{M-b_L}h(b_L)^{u_L}, \tag*{(12)}

which consists of one multiplier per nonfinal block, and a factor for the final block.

Prefixes with the same boundary can be merged. The factors in (11) depend only on the block’s start and end boundaries, not on earlier blocks. Consider the first i<Li<L blocks of a representing sequence. We define a prefix to consist of these ii blocks together with bi+1b_{i+1}. (Note that the end boundary of block ii is bi+1b_{i+1}.) The weight of the prefix is

∏j=1iτ(kj−1,bj;kj,bj+1).\prod_{j=1}^{i}\tau(k_{j-1},b_j;k_j,b_{j+1}).

Now extend a prefix by a nonfinal block with start boundary (ℓ,b)(\ell,b) and end boundary (r,c)(r,c). Recall that each representing sequence corresponds to a single summand in (9), which (12) factors into blockwise multipliers. Thus, for any complete representing sequence extending the prefix, its contribution to (9) factors via (12) as

(weight of the prefix)×τ(ℓ,b;r,c)×(factors of the later blocks).\text{(weight of the prefix)}\times\tau(\ell,b;r,c)\times\text{(factors of the later blocks)}.

The multiplier τ(ℓ,b;r,c)\tau(\ell,b;r,c) is the same for every prefix ending at (ℓ,b)(\ell,b). We can therefore sum the weights of these prefixes before extending them.

States and recurrence. Define the forward state F[ℓ,b]F[\ell,b] as the sum of the weights of all prefixes ending at (ℓ,b)(\ell,b). The empty prefix has the empty forbidden set and is initialized to

F[0,0]=1.(13)F[0,0]=1. \tag*{(13)}

All other entries are initially zero. By the binomial convention, τ(ℓ,b;r,c)\tau(\ell,b;r,c) in (11) vanishes unless z≤rz \le r and c>rc > r, so only such entries are assigned below. Extending the prefixes that end at each boundary (ℓ,b)(\ell,b) to (r,c)(r,c) gives, for z≤r<Mz \le r < M and r<c≤Mr < c \le M,

F[r,c]=∑ℓ=0r−1∑b=0c−1F[ℓ,b] τ(ℓ,b;r,c).(14)F[r,c] = \sum_{\ell=0}^{r-1}\sum_{b=0}^{c-1} F[\ell,b]\,\tau(\ell,b;r,c). \tag*{(14)}

A final block takes the terminal factor of (12) with all remaining items, so

Nbad=∑ℓ=0M−1∑b=0MF[ℓ,b](M−ℓ−1M−b)h(b)n−ν(ℓ).(15)N_{\mathrm{bad}} = \sum_{\ell=0}^{M-1}\sum_{b=0}^{M} F[\ell,b]\binom{M-\ell-1}{M-b}h(b)^{n-\nu(\ell)}. \tag*{(15)}

Each summand F[ℓ,b]τ(ℓ,b;r,c)F[\ell,b]\tau(\ell,b;r,c) of (14) extends the prefixes ending at (ℓ,b)(\ell,b) by one block. By induction on ℓ\ell, the recurrence computes F[ℓ,b]F[\ell,b] as defined, and (15) equals the sum (9).

With O(M2)O(M^2) states and O(M2)O(M^2) predecessors per state, the recurrence uses O(M4)O(M^4) integer operations and O(M2)O(M^2) cells. Its states depend on MM; the next subsection removes this dependence.

Faster evaluation and reuse across table sizes

We further improve the algorithm to O(n2log⁡n)O(n^2 \log n) by combining three observations.

First, after the initial block of degree 0, the total weight of the remaining blocks depends only on the numbers of remaining real items p=M−ℓp=M-\ell and available slots v=M−bv=M-b, where $0 \le v < p \le n$. We call the remaining blocks a suffix and let V[p,v]V[p,v] denote their total weight. This gives O(n2)O(n^2) states independent of the table size MM.

Second, in the recurrence for V[p,v]V[p,v], the inner sum over the next available-slot count ww depends only on vv and the next item count qq, but not on pp. Reusing these shared sums splits the transition into two stages and reduces the complexity from O(n4)O(n^4) to O(n3)O(n^3).

Third, the binomial coefficients in both stages can be rearranged into convolution kernels, allowing both the shared sums and the suffix weights to be computed using polynomial multiplication. Using FFT-based polynomial multiplication, the complexity is reduced to O(n2log⁡n)O(n^2 \log n).

Independent draws with replacement

Suppose instead that each item makes dd independent uniform draws from [M][M]. Its sampling outcome is an ordered dd-tuple, so Q=MdQ=M^d. Of these, h(b)=(M−b)dh(b)=(M-b)^d avoid a forbidden set of size bb. Apart from these two counts, the algorithms in this section stay unchanged.

Evaluation for separate tables

The model and the state

There are dd disjoint tables of positive lengths m1,…,mdm_1,\ldots,m_d. Each item chooses one slot uniformly from each table, independently across tables and items, and must occupy one of these slots. Write m=(m1,…,md)\mathbf{m}=(m_1,\ldots,m_d), M=∑jmjM=\sum_j m_j, and Q=∏jmjQ=\prod_j m_j. There are QnQ^n equally likely outcomes; let Nbad(n;m)N_{\mathrm{bad}}(n;\mathbf{m}) count those admitting no valid placement. We consider d<n<Md<n<M.

The recurrence in § 3.2 tracks the total number of forbidden slots bb. For separate tables, we need to track the number of forbidden slots in each table. For example, with two tables of length 4, the forbidden counts (3,1)(3,1) and (2,2)(2,2) both total four but leave 1⋅3=31\cdot3=3 and 2⋅2=42\cdot2=4 candidate choices per item, respectively. Let b=(b1,…,bd)\mathbf{b}=(b_1,\ldots,b_d) denote the number of forbidden slots in each table, and write ∣b∣=∑jbj|\mathbf{b}|=\sum_j b_j. An item whose forbidden set has counts b\mathbf{b} has

hm(b)=∏j=1d(mj−bj)(16)h_{\mathbf{m}}(\mathbf{b})=\prod_{j=1}^{d}(m_j-b_j) \tag*{(16)}

candidate choices.

For two consecutive blocks, let b\mathbf{b} and c=(c1,…,cd)\mathbf{c}=(c_1,\ldots,c_d) denote the counts of their respective forbidden sets in each table. The latter is obtained from the former by choosing cj−bjc_j-b_j additional slots from the mj−bjm_j-b_j remaining slots in each table jj. The number of possible choices is

(m−bc−b)=∏j=1d(mj−bjcj−bj).(17)\binom{\mathbf{m}-\mathbf{b}}{\mathbf{c}-\mathbf{b}}=\prod_{j=1}^{d}\binom{m_j-b_j}{c_j-b_j}. \tag*{(17)}

This binomial notation will also be used for other quantities.

The forward recurrence

Define the forward state Fd[ℓ,b]F_d[\ell,\mathbf{b}] as in § 3.2: the sum of the weights of all prefixes that end at left vertex ℓ\ell with a forbidden set of counts b\mathbf{b}.

The multiplier (11) changes in two places: the candidate count h(b)h(\mathbf{b}) becomes hm(b)h_{\mathbf{m}}(\mathbf{b}), and the set extension (M−bc−b)\binom{M-\mathbf{b}}{\mathbf{c}-\mathbf{b}} becomes (m−bc−b)\binom{\mathbf{m}-\mathbf{b}}{\mathbf{c}-\mathbf{b}}. The coefficient factor and the item-choice factor are unchanged:

τd(ℓ,b;r,c)=ϕ(∣c∣−ℓ,∣b∣−ℓ,r−ℓ)(m−bc−b)(n−ν(ℓ)u)hm(b)u,(18)\tau_d(\ell,\mathbf{b};r,\mathbf{c})=\phi(|\mathbf{c}|-\ell,|\mathbf{b}|-\ell,r-\ell)\binom{\mathbf{m}-\mathbf{b}}{\mathbf{c}-\mathbf{b}}\binom{n-\nu(\ell)}{u}h_{\mathbf{m}}(\mathbf{b})^u, \tag*{(18)}

with u=r−max⁡{ℓ,z}u=r-\max\{\ell,z\}, z=M−nz=M-n dummy items, and ν(ℓ)=max⁡{0,ℓ−z}\nu(\ell)=\max\{0,\ell-z\} as before. Initialize Fd[0,0]=1F_d[0,\mathbf{0}]=1 and all other entries to zero. For z≤r<Mz\le r<M and 0≤c≤m\mathbf{0}\le\mathbf{c}\le\mathbf{m} with ∣c∣>r|\mathbf{c}|>r,

Fd[r,c]=∑ℓ=0r−1 ∑0≤b<cFd[ℓ,b] τd(ℓ,b;r,c).(19)F_d[r,\mathbf{c}]=\sum_{\ell=0}^{r-1}\ \sum_{\mathbf{0}\le\mathbf{b}<\mathbf{c}}F_d[\ell,\mathbf{b}]\,\tau_d(\ell,\mathbf{b};r,\mathbf{c}). \tag*{(19)}

A final block takes all remaining items, so

Nbad(n;m)=∑ℓ=0M−1 ∑0≤b≤mFd[ℓ,b](M−ℓ−1M−∣b∣)hm(b)n−ν(ℓ),(20)N_{\mathrm{bad}}(n;\mathbf{m})=\sum_{\ell=0}^{M-1}\ \sum_{\mathbf{0}\le\mathbf{b}\le\mathbf{m}}F_d[\ell,\mathbf{b}]\binom{M-\ell-1}{M-|\mathbf{b}|}h_{\mathbf{m}}(\mathbf{b})^{n-\nu(\ell)}, \tag*{(20)}

and the failure probability is Nbad(n;m)/QnN_{\mathrm{bad}}(n;\mathbf{m})/Q^n.

Complexity

Apart from (0,0)(0,0), the recurrence (19) produces states with z≤ℓ<Mz \le\ell< M and ∣b∣>ℓ|\mathbf{b}| > \ell only. If bj=mjb_j = m_j for some jj, then hm(b)=0h_{\mathbf{m}}(\mathbf{b}) = 0: every later item lacks a candidate in table jj, so every transition from the state and its term in (20) vanish. We therefore keep only states with bj<mjb_j < m_j for every jj. Put p=M−ℓp = M - \ell and v=m−b\mathbf{v} = \mathbf{m} - \mathbf{b} for the remaining items and the available slots in each table. The retained states satisfy

1≤p≤n,v≥1,∣v∣<p.1 \le p \le n,\qquad\mathbf{v} \ge1,\qquad|\mathbf{v}| < p.

For each pp there are at most (p−1d)\binom{p-1}{d} such vectors v\mathbf{v}, so the recurrence has at most

1+∑p=1n(p−1d)=1+(nd+1)=O(nd+1)1 + \sum_{p=1}^{n} \binom{p-1}{d} = 1 + \binom{n}{d+1} = O(n^{d+1})

states. Each state is computed by enumerating all retained predecessors and applying (18). With the binomial coefficients and the powers of hmh_{\mathbf{m}} precomputed, a transition costs O(1)O(1) operations. Hence the recurrence uses O(n2d+2)O(n^{2d+2}) integer operations and O(nd+1)O(n^{d+1}) cells for each table-length vector m\mathbf{m}. This is polynomial in nn for every constant dd.

Faster evaluation. The suffix formulation of § 3.3 also applies to separate tables. Tracking suffixes by the number of remaining items and the available counts in each table gives a table that depends only on nn and dd. Sharing inner sums and applying two binomial transforms builds it in O(nd+2)O(n^{d+2}) operations, after which each table-length vector is evaluated in O(nd+1)O(n^{d+1}) operations.

Conclusion

We present dynamic programming algorithms for the exact failure probability of dd-choice cuckoo hashing for both the one-table and separate-table variants. The algorithms evaluate Beniamini’s expansion by combining prefixes with the same block boundary. For the one-table variant, our algorithm runs in O(n2log⁡n)O(n^2 \log n) time. For the separate-table variant, our algorithm runs in O(nd+2)O(n^{d+2}) time for constant dd. A direction for future work is to find an algorithm for separate tables that is polynomial in both nn and dd.

References

  1. [1][ACLS18] Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. PIR with compressed queries and amortized query processing. In 2018 IEEE Symposium on Security and Privacy (SP), pages 962–979. IEEE, 2018.DOI
  2. [2][Ben22] Gal Beniamini. The approximate degree of bipartite perfect matching. In Proceedings of the 37th Computational Complexity Conference, CCC ’22, Dagstuhl, DEU, 2022. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  3. [3][BN21] Gal Beniamini and Noam Nisan. Bipartite perfect matching as a real polynomial. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1118–1131, 2021.
  4. [4]Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink. Tight thresholds for cuckoo hashing via xorsat. In International Colloquium on Automata, Languages, and Programming, pages 213–225. Springer, 2010.arxiv.org/abs/0912.0287
  5. [6]Bin Fan, David G. Andersen, and Michael Kaminsky. MemC3: Compact and concurrent Mem-Cache with dumber caching and smarter hashing. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), pages 371–384. USENIX Association, 2013.
  6. [7]Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, pages 75–88. ACM, 2014.
  7. [8]Alan Frieze and Páll Melsted. Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Structures & Algorithms, 41(3):334–364, 2012.DOI
  8. [9]Nikolaos Fountoulakis and Konstantinos Panagiotou. Sharp load thresholds for cuckoo hashing. Random Structures & Algorithms, 41(3):306–333, 2012.arxiv.org/abs/0910.5147
  9. [10]Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul Spirakis. Space efficient hash tables with worst case constant access time. Theory of Computing Systems, 38(2):229–248, 2005.
  10. [11]Michael T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In International Colloquium on Automata, Languages, and Programming, pages 576–587. Springer, 2011.arxiv.org/abs/1007.1259
  11. [12]Reinhard Kutzelnigg. Bipartite random graphs and cuckoo hashing. In Fourth Colloquium on Mathematics and Computer Science, volume AG of DMTCS Proceedings, pages 403–406, 2006.DOI
  12. [13]Reinhard Kutzelnigg. Random Bipartite Graphs and their Application to Cuckoo Hashing. PhD thesis, Technische Universität Wien, 2008.
  13. [14]Reinhard Kutzelnigg. A further analysis of cuckoo hashing with a stash and random graphs of excess r. Discrete Mathematics & Theoretical Computer Science, 12(3):81–102, 2010.DOI
  14. [15]Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–144, 2004.
  15. [16]Ely Porat and Bar Shalem. A cuckoo hashing variant with improved memory utilization and insertion time. In 2012 Data Compression Conference, pages 347–356. IEEE, 2012.arxiv.org/abs/1104.5400
  16. [17]Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium, pages 515–530. USENIX Association, 2015.
  17. [18]Dimitrios Skarlatos, Apostolos Kokolis, Tianyin Xu, and Josep Torrellas. Elastic cuckoo page tables: Rethinking virtual memory translation for parallelism. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1093–1108, 2020.
  18. [19]Kevin Yeo. Cuckoo hashing in cryptography: Optimal parameters, robustness and applications. In Advances in Cryptology – CRYPTO 2023, pages 197–230. Springer Nature Switzerland, 2023.arxiv.org/abs/2306.11220
  19. [20]Dong Zhou, Bin Fan, Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. Scalable, high performance ethernet forwarding with cuckooswitch. In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, pages 97–108, 2013.DOI

Paper details

vlnc:W_m4mwazfs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents