Papers › Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, Jonatan Ziegler
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Randomised algorithms often employ methods that can fail and that are retried with independent randomness until they succeed. Randomised data structures therefore often store indices of successful attempts, called seeds. If n such seeds are required (e.g., for independent substructures) the standard approach is to compute for each i ∈[n] the smallest successful seed Sᵢ and store S⃗ = (S₁, …, Sₙ). The central observation of this paper is that this is not space-optimal. We present a different algorithm that computes a sequence S⃗′ = (S₁′, …, Sₙ′) of successful seeds such that the entropy of S⃗′⃗ undercuts the entropy of S⃗ by Ω(n) bits in most cases. To achieve a memory consumption of OPT+εn, the expected number of inspected seeds increases by a factor of O(1/ε). We demonstrate the usefulness of our findings with a novel construction for minimal perfect hash functions that, for n keys and any ε∈[n^(-3/7), 1], has space requirement (1+ε)OPT and construction time O(n/ε). All previous approaches only support ε= ω(1 / logn) or have construction times that increase exponentially with 1/ε. Our implementation beats the construction throughput of the state of the art by more than two orders of magnitude for ε≤3%.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections