PaperlayerView exact revision on arXiv

Source-linked AI summary

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

Yuriy Arbitman, Moni Naor, Gil Segev

arXiv:0912.5424v3cs.DS

TL;DR

Dynamic dictionaries have known constructions with constant-time worst-case operations or near-optimal space, but combining those guarantees remains challenging. This paper uses cuckoo-hashing variants, including permutation-based hashing, to construct dictionaries with both properties. The constructions provide constant-time worst-case operations with high probability, including a variant using near-information-theoretic space.

  • Problem

    Known dynamic dictionaries offered constant-time worst-case operations or essentially optimal space, but combining strong guarantees for update time, lookup time, and space remained challenging.

    Source: §1 · p. 2

  • Method

    The paper develops a two-level cuckoo-hashing construction with de-amortized perfect hashing and a succinct permutation-based variant.

    Source: §1.1 · pp. 2–3

  • Results

    The constructions use (1 + ε)n words or, in the succinct variant, (1 + o(1))B bits while providing constant-time worst-case operations with high probability.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    The succinct dictionary can also yield a deletion-supporting Bloom-filter alternative with worst-case constant-time operations, unlike the cited prior solution’s amortized guarantees.

    Source: §6 · p. 28

    The construction assumes a predetermined maximum number of stored elements; achieving full memory utilization during dynamic resizing remains open.

    Source: §6 · p. 28

Abstract

from arXiv · show

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: - We construct the first dynamic dictionary that enjoys the best of both worlds: it stores n elements using (1+epsilon)n memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any epsilon = \Omega((\log\log n / \log n)^{1/2} ) and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of epsilon. The construction is a two-level variant of cuckoo hashing, augmented with a "backyard" that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on epsilon. - We present a variant of the above construction that uses only (1+o(1))B bits, where B is the information-theoretic lower bound for representing a set of size n taken from a universe of size u, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the amortized setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe.

1 Introduction

The paper addresses the challenge of combining near-optimal space with constant-time worst-case dictionary operations. It presents two cuckoo-hashing constructions and places them against prior work on worst-case performance, memory utilization, and succinct representations.

1.1 Our Contributions

  • For ε = Ω((log log n / log n)^1/2), a two-level cuckoo-hashing dictionary uses (1 + ε)n words and supports constant-time worst-case operations independent of ε.The guarantees hold with high probability over initialization for polynomially many operations.Source: §1.1 · pp. 2–3
  • The succinct variant uses (1 + o(1))B bits while retaining constant-time worst-case operations with high probability.It hashes elements using permutations and replaces truly random permutations with k-wise δ-dependent permutations.Source: §1.1 · p. 3
  • Permutation-based cuckoo hashing stores n elements in (2 + ε)n log(u/n) bits instead of (2 + ε)n log u bits.The paper says this saving may be especially significant for small universes; its analysis uses a coupling between a random function and a random permutation.Source: §1.1 · p. 3
  • For sub-constant δ and u ≤ 2^O(n), the approximate-membership construction uses (1 + o(1))n log(1/δ) + O(n + log u) bits with constant-time worst-case lookups and insertions.Its operation times are independent of δ, and its space is optimal up to an additive lower-order term under those conditions.Source: §1.1 · pp. 3–4

1.2 Related Work

  • Earlier worst-case dictionaries had large multiplicative constants or about 50% memory utilization, while linear probing and generalized cuckoo schemes presented other time-space trade-offs.The cited prior work also includes multi-level dictionaries whose deletion support or operation times depend on the number of levels.Source: §1.2 · p. 4
  • Prior dictionaries approaching the information-theoretic space bound offered amortized guarantees or did not efficiently support deletions; another cited construction used O(B) bits with worst-case guarantees.The paper relates its permutation approach to quotient hash functions used in that earlier construction.Source: §1.2 · p. 5

1.3 Paper Organization

  • The paper proceeds from tools and a first construction to de-amortization, then presents the succinct variant and concluding open problems.Appendix A discusses a Bloom-filter alternative, and Appendix B discusses negatively related random variables used in the analysis.Source: §1.3 · p. 5

2 Preliminaries and Tools

This section introduces limited-independence tools for the paper’s analyses and constructions. It also describes approximate-independence guarantees and tail bounds used when variables are dependent.

k-wise independent functions

  • A k-wise independent function collection makes outputs on any k distinct inputs jointly uniform; polynomials of degree k − 1 over a finite field are one example.For functions from U to V, each specified output tuple has probability 1/|V|^k.Source: §2 · p. 5
  • Siegel’s construction supplies functions with short representations and constant-time evaluation, with n^α-wise independence holding with probability at least 1 − n^−c.The functions use n^β bits for constants α < β < 1.Source: §2 · pp. 5–6
  • The weaker guarantee for a function collection does not identify one polynomially unlikely bad event whose absence ensures k-wise independence.It need not hold simultaneously over all subsets of size k, though the paper later shows its constructions can use this guarantee.Source: §2 · p. 6

k-wise almost independent permutations

  • A k-wise δ-dependent permutation collection approximates the output distribution of a truly random permutation in statistical distance; exact k-wise independent constructions are not known here for k > 3.The paper observes a short-description, constant-evaluation-time construction of such permutations.Source: §2 · p. 6

Deviation inequalities for random variables with limited independence

  • For dependent-variable tail bounds, the paper uses limited-independence inequalities and Janson’s method for negatively related variables.Negative relation is described informally as one variable’s above-expected value accompanying lower values in others.Source: §2 · p. 7

3 The Backyard Construction

The backyard construction combines a first-level bin table with second-level cuckoo hashing to use space efficiently while supporting worst-case operations. With high probability, few elements overflow the bins, allowing the second level to remain small.

3 The Backyard Construction

  • A first-level table of m bins, each holding d elements, stores each item in its bin or in a second-level dictionary; lookup checks both levels.The second level is sized for at most ǫn/16 elements after n insertions, with high probability.Source: §3 · p. 7
  • Cuckoo hashing supports movement from the second level back into newly available first-level bin space, keeping the second level limited to overflowing elements.The insertion procedure checks whether encountered elements fit in their first-level bin; if one does, the current nestless element can use the available second-level position.Source: §3 · pp. 7–8
  • De-amortized cuckoo hashing limits second-level insertion work to L moves per operation, leaving unfinished work in a queue.The construction uses the Arbitman et al. scheme, including its stash to avoid rehashing.Source: §3 · p. 8
  • The dictionary stores n elements in (1 + ǫ)n memory words, with worst-case operation times O(log(1/ǫ)/ǫ2) under the theorem’s stated probability guarantees.For polynomially many operations, insertions meet the bound with high probability over initialization; deletions and lookups always meet it.Source: §3 · p. 9
  • For any fixed set of n elements, k-wise independent hashing leaves at least (1 − ǫ/16)n elements in non-overflowing bins with probability 1 − 2^-ω(log n).An element is overflowing when its bin contains at least d other elements.Source: §3 · pp. 9–10
  • Across polynomially many operations, the bound on overflowing elements at every step suffices for the stated worst-case time guarantees.The proof applies a union bound over the operation sequence, then relates second-level insertions to de-amortized cuckoo hashing.Source: §3 · pp. 11–12

4 De-amortized Perfect Hashing: Eliminating the Dependency on ǫ

The section augments first-level bins with de-amortized perfect hashing and a shared queue to remove the dependence on ǫ from operation times. The resulting dictionary uses (1 + ǫ)n words for ǫ = Θ((log log n/ log n)1/2) and supports constant-time operations in the worst case with high probability.

4 De-amortized Perfect Hashing: Eliminating the Dependency on ǫ

  • For ǫ = Θ((log log n/ log n)1/2), the dictionary uses (1 + ǫ)n words and performs all operations in constant worst-case time, independent of ǫ, with high probability.The guarantee applies to any polynomial-length operation sequence with at most n stored elements.Source: §4 · p. 12

4.1 A Specific Scheme for ǫ = Ω((log log n/ log n)1/2)

  • The specific perfect-hashing scheme restricts the supported range to ǫ = Ω((log log n/ log n)1/2) because of hash-function description length and computation overhead.Its lookup uses h(x) to obtain r and then g(r) to check whether x is stored there.Source: §4 · p. 13, §4.1 · pp. 15–16

4 De-amortized Perfect Hashing: Eliminating the Dependency on ǫ

  • A shared queue processes a constant number of steps per insertion, and the analysis bounds its size by O(log n) with high probability.The expected work per element is a small constant; the number of steps per operation can be chosen independently of ǫ.Source: §4 · pp. 12–13

5 Matching the Information-Theoretic Space Bound

This section develops and analyzes a permutation-based two-level dictionary that approaches the information-theoretic space bound while preserving worst-case constant-time operations with high probability. It refines both levels and establishes guarantees for bin loads and within-bin handling using limited-independence mappings.

5.1 A Scheme based on Truly Random Permutations

  • The first level uses a chopped permutation: its leftmost log m bits select the bin, while its remaining bits identify the element within that bin.The construction retains the two-level structure, with de-amortized cuckoo hashing in the second level for overflowing elements.Source: §5.1.1 · p. 17, §5.1 · p. 17

5.1.1 First-Level Hashing Using Permutations

  • For d = O(log(1/ε)/ε^2), at most εn/16 elements overflow the first-level bins with overwhelming probability under a truly random permutation.An element overflows when its bin contains at least d other elements.Source: §5.1.1 · p. 17

5.1.2 The Bins in the First-Level Table

  • The bin scheme selects representations based on the ratio u/n while bounding function descriptions and lookup-table space so first-level operations remain constant-time independent of bin size.The construction considers separate cases for u ≤ n · 2^(log n)^β and u > n · 2^(log n)^β, for β < 1.Source: §5.1.2 · pp. 18–19

5.1.3 The Second Level: Permutation-based Cuckoo Hashing

  • With probability 1 − e^-Ω(ε^3n), a cuckoo graph from two truly random permutations is a subgraph of the corresponding graph from truly random functions.The permutation-based second level uses the leftmost log r bits for table locations and the rightmost log(u/r) bits as element identities, enabling roughly log(u/n) bits per element.Source: §5.1.3 · pp. 19–20

5.1.4 The Total Memory Utilization

  • At most (1 + 3ε)B bits are used in total by the construction.The second level uses at most εB bits; the first-level hash-function and global-lookup-table overhead is bounded by εB/6.Source: §5.1.4 · pp. 21–22

5.2 A Scheme based on k-wise δ-dependent Permutations

  • The k-wise δ-dependent scheme divides the elements among n^9/10 bins and achieves the truly random scheme’s performance guarantees with probability 1 − 1/poly(n).It uses shared one-round Feistel permutations and sets k = n^1/10 + n^3/40; each bin’s distribution is δ-close to that under truly random permutations.Source: §5.2 · pp. 22–23
  • With k′=⌊n^1/20/e^1/3⌋, the mapping places at most n^1/10+n^3/40 elements in any of n^9/10 bins with probability 1−2^−ω(log n).The proof partitions elements by their xR values; the resulting indicators are k′-wise independent, and a limited-independence Chernoff bound controls the bin load.Source: §5.2 · p. 23

5.4 Using More Efficient Hash Functions

  • Theorem 5.1 still holds when the scheme replaces its hash functions with Dietzfelbinger and Woelfel functions, despite their weaker randomness guarantee.For a specified set, these functions may fail with polynomially small probability; otherwise, they are fully random on that set.Source: §5.4 · p. 25
  • For first-level bin mapping, Claim 5.7 bounds each bin’s load by n^1/10+n^1/20 log n with probability at least 1−n^−(c−1).It uses functions that are uniform on each specified set of n/log^2 n elements with probability at least 1−n^−c.Source: §5.4 · p. 26
  • For handling elements within first-level bins, Corollary 5.8 gives constant-time permutations described in O(k log n) bits, enabling better space consumption and evaluation time.The randomness guarantee is weaker than Corollary 5.5’s, but the shorter descriptions allow slightly larger first-level bins.Source: §5.4 · pp. 26–27

6 Concluding Remarks and Open Problems

The concluding remarks discuss amortized benefits and practical variants, then identify open problems in failure probability, parameter ranges, permutations, and dynamic resizing. They also note applications to multisets and deletion-capable Bloom-filter alternatives.

Implications of our constructions for the amortized setting

  • With classical cuckoo hashing, the construction offers a logarithmic high-probability update-time bound and (1 + ǫ)n memory words for sub-constant ǫ, even amortized.This variant replaces the de-amortized cuckoo hashing used in the main construction.Source: §6 · p. 27

On the practicality of our schemes

  • A small queue may let a practical variant avoid second-level cuckoo hashing, while two-choice or generalized cuckoo hashing in first-level bins can reduce overflow.Experiments indicate sometimes dramatic improvements for these approaches; the queue-based variant stores an element in one of two first-level bins or the queue.Source: §6 · p. 27

Clocked adversaries

  • The worst-case guarantee can help protect against clocked adversaries, but answering every request at the worst-case probe bound may waste resources and ignore memory hierarchy.The proposed fixed-time approach uses an upper bound on each memory-access time and answers every request in that bound times the worst-case number of probes.Source: §6 · p. 27

Lower bounds for dynamic dictionaries

  • Reducing the failure probability to sub-polynomial remains open; identified bottlenecks include approximating k-wise functions or permutations and queue lookup.For polynomial-size universes, the queue can in fact be maintained deterministically.Source: §6 · pp. 27–28

Extending the scheme to smaller values of ǫ

  • The perfect-hashing augmentation handles ǫ = Ω((log log n / log n)1/2); its overhead comes from global lookup-table space and per-bin hash-function description and adjustment.Using two choices to reduce first-level overflow is proposed as one possible route to smaller ǫ.Source: §6 · p. 28

Constructions of k-wise almost independent permutations

  • Open problems for succinct k-wise δ-dependent permutations include larger k and sub-polynomial δ, with cited constructions imposing restrictions on k and Siegel’s construction limiting failure probability.The stated bottlenecks are k < u1/2 in, k ≤nα in, and the failure probability of.Source: §6 · p. 28

Supporting dynamic resizing

  • The construction assumes a predetermined maximum number of stored elements; achieving (1 + o(1))ℓ memory words as occupancy changes requires low-overhead dynamic resizing.The first-level bins can be resized relatively simply, but full memory utilization at any time remains an open goal.Source: §6 · p. 28

Dealing with multisets

  • A succinct multiset dictionary with constant-time worst-case operations could yield a deletion-capable Bloom-filter alternative to Pagh et al.’s amortized-time construction.The cited manuscript on a cell-probe lower bound is reported as having unclear results.Source: §6 · p. 28

A Application of Small Universes: A Nearly-Optimal Bloom Filter Alternative

Dynamic approximate set membership requires low space and fast lookups while allowing false positives but no false negatives. Applying Carter et al.’s method to the succinct dictionary gives a Bloom-filter alternative with near-optimal space and worst-case constant-time insertions with high probability.

Application context

  • Dynamic approximate set membership represents an insertion-defined set, permits false positives at rate at most δ, and requires no false negatives.Its information-theoretic space lower bound is n log(1/δ) bits, even for static sets [CFG+78].Source: A Application of Small Universes: A… · p. 33

A general solution using a dictionary

  • Carter et al.’s method hashes set elements into [n/δ] and stores the hashed set in a dictionary.Universal hashing gives nonmembers a correct lookup result with probability at least 1 − δ; an insertion-capable dictionary allows elements to be provided one by one.Source: A Application of Small Universes: A… · p. 33

Related approaches

  • The earlier Pagh et al. alternative supports insertions and deletions in amortized expected constant time, while Bloom filters have lookup time dependent on δ and sub-optimal space.The Pagh et al. construction uses (1 + o(1))n log(1/δ)+O(n+log u) bits and constant lookup time independent of δ.Source: A Application of Small Universes: A… · p. 33

Using our succinctly-represented dictionary

  • The dictionary-based alternative uses (1 + o(1))n log(1/δ) + O(n + log u) bits, with constant lookup time independent of δ and worst-case constant-time insertions with high probability.For sub-constant δ and u ≤ 2O(n), its space is (1 + o(1))n log(1/δ), optimal up to an additive lower-order term.Source: A Application of Small Universes: A… · p. 34

B Negatively Related Random Variables

The appendix uses negative relation to justify applying Chernoff bounds to dependent indicator variables. It constructs related indicators by conditioning a bin to exceed a threshold and moving balls into it.

Use of negative relation

  • The authors apply Chernoff bounds to these non-independent, negatively related indicators in the proofs of Lemmata 3.2 and 5.2.Janson showed that these bounds apply in this setting.Source: B Negatively Related Random Variables · p. 34

Definition and construction

  • For each j, the constructed indicators J_i,j have the same joint distribution as I_i, as required by the definition of negative relation.The definition specifies indicator variables on the same probability space or an extension of it.Source: B Negatively Related Random Variables · p. 34

Negative relation construction

  • The proof of Lemma 3.2 maps n balls uniformly and independently into m bins and marks bins containing at least t balls with indicators I_i.When a selected bin falls below t, balls are moved into it to construct the related indicators J_i,j.Source: B Negatively Related Random Variables · p. 34

Chopped-permutation variant

  • For Lemma 5.2, balls are mapped using a chopped permutation; moving balls between bins then requires swapping permutation values at selected occupied and empty locations.The empty locations are chosen in the destination bin, and the selected balls come from other bins.Source: B Negatively Related Random Variables · p. 34

Related papers

Loading 0912.5424v3…