PaperlayerView exact revision on arXiv

Source-linked AI summary

Consensus for Compressed Static Functions

Dominik Rosch, Jonatan Ziegler

arXiv:2609.39557v1cs.DS

TL;DR

Compressed static functions aim to approach the empirical entropy of nonuniform values, but existing structures do not combine arbitrary closeness with a practical implementation. Consensus-CSF uses task insertions to balance one-bit tasks and achieves an entropy–construction-time tradeoff. Its implementation reaches space overheads in the competitors’ order of magnitude, but does not outperform them.

  • Problem

    Existing CSFs either cannot approach the entropy bound arbitrarily closely or are impractical and unimplemented.

    Source: §1 · p. 2

  • Method

    Consensus-CSF maps keys to one-bit Consensus tasks and inserts tasks into groups to balance task difficulty and key weight.

    Source: §1 · p. 2, §1.2 · p. 3

  • Results

    The implemented algorithm reaches space usage mostly in the same order of magnitude as competitors but never dominates them.

    Source: §6 · p. 22

  • Takeaways & Limitations

    Consensus can extend to the less structured CSF setting, achieving nH0(1 + δ) space with construction time n exp(Õ(√(1/δ))) under stated value-distribution assumptions.

    Source: §6 · p. 22

    Construction is too expensive for small space overheads in practice, and the asymptotic analysis shows its effects only where construction is already impractical.

    Source: §5.3 · p. 22

Abstract

from arXiv · show

The Consensus technique marked a breakthrough in the construction of minimal perfect hash functions (MPHFs), reaching a linear tradeoff between construction time and space overhead relative to the optimum. Consensus provides a clever scheme to search for and encode seeds of tasks in random data structures. We apply Consensus to the related field of compressed static functions (CSFs). These data structures store a function $f: S \to \Sigma$ such that querying a key $x \in S$ returns $f(x)$ and querying $x \not \in S$ returns an arbitrary value. CSFs do not need to store the keys $S$ and only need space close to the zeroth-order empirical entropy of the multiset of values. Often, some values are much more common than others. In these cases, CSFs can use less space than their non-compressed counterparts. CSFs are a useful building block, for example in database design and bioinformatics. We introduce Consensus-CSF, which can reach arbitrarily close to the empirical entropy $n H_0$, with a construction time of $n \exp(\tilde{\cal{O}} (\sqrt{1 / \delta}))$ for space usage of $n H_0 (1 + \delta)$ when assuming some parameters of the value distribution to be constants. This tradeoff beats previously implemented approaches that can only reach some fixed threshold above the entropy lower bound. We enable Consensus in the setting of CSFs, which is less structured than MPHFs, with the introduction of task insertions. Our approach randomly distributes the keys into one-bit Consensus tasks and then strategically inserts additional tasks in places where the construction would get stuck otherwise. We provide an implemented version of our algorithm which reaches the same order of magnitude in space overhead as competitors but is not competitive in practice. Beyond these results, we present a new way to think and reason about Consensus, which may also be applied to other problems.

1 Introduction

Compressed static functions target the zeroth-order empirical entropy of nonuniform values, but prior approaches could not combine arbitrarily low space overhead with an implementation. Consensus-CSF applies Consensus using task insertions and offers an entropy–construction-time tradeoff under stated distribution assumptions.

1 Introduction

  • For nonuniform value frequencies, compressed static functions target nH0 space, where H0 is the zeroth-order empirical entropy of the values.The setting does not assume correlation between keys and values.Source: §1 · p. 2
  • Prior CSF structures either cannot approach the entropy bound arbitrarily closely or are theoretical and unimplemented.The paper targets the gap between those space and practicality goals.Source: §1 · p. 2
  • Consensus-CSF assigns keys to one-bit tasks, inserts tasks into overloaded groups, and uses a fallback when insertion or key mapping remains insufficient.Its balancing scheme accounts for the information content, or weight, of keys with different value frequencies.Source: §1 · p. 2

1.2 Results & Contribution

  • The algorithm has constant query time and uses nH0(1 + δ) space with construction time n exp(Õ(√(1/δ))), assuming some value-distribution properties are constants.The paper also provides an implementation and compares it with previous approaches.Source: §1.2 · p. 3

2 Related Work

Earlier CSF approaches either remain theoretical or incur fixed linear overhead, while Consensus provides a seed-search framework based on bounded tries and backtracking. The paper introduces Consensus and its seed encoding, with one-bit tasks for its CSF application.

2 Related Work

  • Belazzougui and Venturini’s CSF approaches nH0 arbitrarily closely for large inputs but is theoretical and has never been implemented [1].It uses a random-value table and stores selected row indices for buckets.Source: §2 · p. 3
  • Linear-equation CSFs use prefix-free codes and a bit array, with the k-XORSAT satisfiability threshold setting array size and space overhead [12].Prefix-free coding can impose up to one bit of overhead; Caramel adds approximate membership filtering for the most common value [3].Source: §2 · pp. 3–4
  • Membership-based CSFs encode coding-tree decisions with weighted relative membership structures, but BuRR-CSF reaches only a fixed linear overhead [11].If its equation system is unsolvable, BuRR bumps keys to a recursive fallback.Source: §2 · p. 4

2.1 Consensus

  • Consensus formulates seed search as finding a bitstring encoding successful try indices for a sequence of Bernoulli-process tasks [17].Its search uses bounded tries with backtracking; Figure 1 depicts the search tree and seed representation.Source: §2.1 · p. 4, Figure 1 · p. 5
  • Consensus can store the successful path through the final-layer seed representation, and changing tries per task tunes the construction-time–space tradeoff.For Consensus-CSF, each task has two tries, corresponding to one stored bit.Source: §2.1 · pp. 4–5

3 Consensus Retrieval Algorithm

Consensus-CSF partitions keys into groups of one-bit tasks and inserts tasks when needed to manage difficult groups. Its construction uses insertion, Consensus, and fallback phases, while queries recover a task seed or use the fallback.

3 Consensus Retrieval Algorithm

  • Inserting β tasks reshuffles a group when its difficulty is poor; if difficulty remains poor, the group’s keys are bumped to a fallback.Each group allows zero, one, or two insertions.Source: §3 · p. 6
  • The structure stores an insertion vector, a Consensus vector, a fallback, and an alias-table hasher..Source: §3 · p. 7
  • Construction first checks groups right-to-left for zero or one insertion, bumps keys when necessary, then runs Consensus to find task seeds and builds the fallback..Source: §3 · p. 7
  • A query hashes the key to a group, uses the insertion vector to locate its task and seed, and returns the seeded hash value or queries the fallback.The insertion count is encoded as contiguous ones preceding the group’s zero separator.Source: §3 · p. 7
  • With |Σ|, I_min, and I_max fixed, construction is linear in n, queries are constant time, and space–time tradeoff is nH0(1 + δ) space to n exp(Õ(√(1/δ))) construction time.The theorem states the guarantee for δ in (0, 2^-cI_max) for some c > 0.Source: §3 · p. 8

4 Analysis

The analysis establishes the construction’s space, construction-time, and query-time bounds by modeling task success probabilities, controlling group failures with insertions and fallback handling, and bounding consensus-vector length. It also accounts for overhead from insertion vectors, select structures, fallbacks, alias tables, and root seeds.

4.1 Formal Setting and Proof Idea

  • The proof models X_t as a random walk in the logarithmic domain, inserting tasks to keep it in bands and bumping groups when insertions do not suffice.For good groups, the curve stays above a loss threshold and within a band; choosing β = √(b log b) makes leaving the bands unlikely over Θ(b) steps.Source: §4.1 · p. 10

4.2 Probability of Good Groups

  • Bad groups occur with probability at most b^-Ω(c), and good-group checks maintain the invariant X_i,m_i ∈ [a + β, a + 2β].Good groups keep the X_t curve within prescribed bands; groups that fail the checks are bumped to the fallback.Source: §4.2 · pp. 11–12

4.3 Bad Group Handling

  • The fallback based on an MPHF and Huffman code from [1] has expected linear construction time, constant query time, and space W_F + N_F log(W_F/N_F + 1) + O(N_F + |Σ|).The analysis bounds fallback space using the bumped keys’ weight W_F and count N_F.Source: §4.3 · pp. 15–16

4.4 Summing up

  • The expected total Consensus-vector length is at most nH_0(1 + O(δ)).This is the length bound proved in Lemma 15.Source: §4.4 · p. 17
  • 𝔼[M] ≤ nH0(1 + O(δ)), so the expected consensus-vector size is within a 1 + O(δ) factor of nH0.The proof bounds good and bad groups and sums their contributions.Source: §4.4 · pp. 17–18
  • Query time is constant, since select queries, hashing, and alias-table access each take constant time in the stated model.The analysis separately accounts for O(|Σ|) alias-table space and linear select-structure overhead.Source: §4.4 · pp. 17–18
  • The insertion vector uses O(δnH0) space, while the fallback structure and root seed contribute additional space overhead.The insertion-vector bound uses one separator bit per group and at most ℓ_i ≤ 2 inserted bits; the fallback-size bound is given in Theorem 12, and the alias table uses O(|Σ|) space.Source: §4.4 · pp. 17–18
  • n exp(Θ(√(1/δ log 1/δ))) bounds the expected number of hash evaluations in the construction.The analysis sums expected evaluations over independently successful keys; fallback construction and select-structure construction are also included in the total-time accounting.Source: §4.4 · p. 18

5 Experiments

The experiments benchmark a modified Consensus-CSF implementation against Caramel and BuRR-CSF on synthetic value distributions. Configurations trade space overhead for construction speed; construction is slower than competitors, and small-overhead settings remain impractical in practice.

5.1 Difference to the Theoretical Algorithm

  • The implementation replaces the fallback structure with repeated task insertions, uses practical hash and select implementations, drops clamping, and tunes D, Db, b, β, and λH0 by grid search.The experiment tests maximum task-difficulty bounds D ∈ {8, 12, 16}.Source: §5.1 · pp. 18–19

5.2 Setup

  • Benchmarks use 10,000,000-key synthetic uniform, Bernoulli, and truncated-geometric datasets, comparing Consensus-CSF with Caramel and BuRR-CSF without parallelism.The datasets vary in value frequencies and range.Source: §5.2 · pp. 19–20

5.3 Results

  • On Ber(0.25), Consensus-CSF configurations trade space overheads of 28%, 15%, and 10% for construction times of 1 µs, 6 µs, and 25 µs per key, respectively.Larger D accepts more difficult tasks, reducing overhead while increasing construction time.Source: §5.3 · p. 20
  • Consensus-CSF constructs significantly more slowly than its competitors: on Ber(0.1), configurations A, B, and C take 0.9, 2.7, and 13.0 µs per key, versus 0.5 for Caramel and 0.3 for BuRR-CSF.All algorithms were run without parallelism.Source: §5.3 · p. 20, §5.2 · p. 20
  • BuRR-CSF has the lowest reported space overhead in the Ber(0.1) example at 10.3%, but its Ber(0.25) overhead is 56.5%, which the authors suspect is an implementation mistake.Configurations A and B also undercut Caramel on inputs with few values.Source: §5.3 · p. 22
  • Consensus configurations A and B use less space than Caramel on few-value inputs but fall behind on larger, heavier-value inputs; configuration C reaches 14.7% overhead on Ber(0.1), near BuRR-CSF, while Caramel reaches 168.6%.Table 2 reports the benchmark values; Figure 5 plots throughput against space overhead.Source: Table 2 · p. 21, §5.3 · p. 22
  • For Ber(0.1), Consensus-CSF query times are 52.6, 50.8, and 50.3 ns for A, B, and C; Caramel is slightly faster at 43.6 ns, while BuRR-CSF takes 73.8 ns.Query times positively correlate with |Σ| across all implementations.Source: §5.3 · p. 22
  • At small δ, the n exp(Õ(√(1/δ))) construction cost is already impractical; for large δ, constant factors dominate.The authors identify other insertion strategies as a possible route to improved space efficiency.Source: §5.3 · p. 22

6 Conclusion

Consensus-CSF reaches space usage nH0(1 + δ) with construction time n exp(Õ(√(1/δ))) under constant value-distribution parameters, while its implementation does not dominate competitors. The authors outline several possible improvements and extensions.

6 Conclusion

  • nH0(1 + δ) space is achieved in n exp(Õ(√(1/δ))) construction time when some value-distribution parameters are constants.This is the theoretical Consensus-CSF tradeoff.Source: §6 · p. 22
  • The modified implementation reaches competitors’ order of magnitude in space for practical construction time, but never dominates them.The conclusion reports this as the implemented algorithm’s experimental result.Source: §6 · p. 22

6.1 Future Work

  • Dynamic programming for task insertion and Huffman-splitting heavy keys are proposed as ways to improve the space–construction-time tradeoff and performance.The current insertion rule uses a hard threshold; Huffman splitting is proposed for cases with many heavy keys.Source: §6.1 · p. 22
  • Filtering the most common values is proposed to make the remaining weights more balanced.Source: §6.1 · p. 23
  • Further theoretical directions include analyzing a version without the fallback data structure and with arbitrary insertions, or exploring different balancing schemes such as weighted k-perfect hashing.Source: §6.1 · p. 23
  • The analyzed Consensus technique could be applied to MPHF bucket placement to achieve faster query times.Source: §6.1 · p. 23

A Table of Variables

The variable overview identifies implementation parameters and summarizes quantities used to describe value weights, task assignment, success probabilities, and changes across groups.

A Table of Variables

  • Variables marked with ⋆ are freely selectable in the implementation, and the overview identifies H0 as the zeroth-order empirical entropy and Imax as the maximum key weight.Source: A Table of Variables · p. 25
  • The parameter c simplifies bounds, while the left-border maximum task difficulty determines when the implementation inserts more tasks.The difficulty condition is stated as log½ qt > Db for task t = (i, 0).Source: A Table of Variables · p. 25
  • The overview defines key-to-task partitions, seed-success probabilities, adjusted task probabilities, a linear-approximation error term, and the change across a group.Source: A Table of Variables · p. 26

B Proofs

The proof excerpts use parameter inequalities and moment-generating-function bounds to support the analysis, including a bound on the random variable W.

B Proofs

  • The Lemma 7 proof uses b = 16 to obtain u = log b ≥ 4 and then compares derivatives for the subsequent inequality.Source: B Proofs · p. 27
  • The Lemma 7 bounds use δ < 1 to obtain ε < 1/4 and use β ≤ b in inequalities involving λH0 and β.Source: B Proofs · p. 27
  • W is expressed as a sum of weighted counts N(α), modeled as independent binomial variables, and convexity is used to bound its moment-generating function.Source: B Proofs · p. 27
Loading 2609.39557v1…