2026-07-23T19:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24578 2025-12-16T14:01:04Z ddc:004 open_access

Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing Lehmann, Hans-Peter Sanders, Peter Walzer, Stefan Ziegler, Jonatan Random Seed Encoding Bernoulli Process Backtracking Perfect Hashing 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_i and store S = (S_1,…,S_n). The central observation of this paper is that this is not space-optimal. We present a different algorithm that computes a sequence S' = (S_1',…,S_n') 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 𝒪(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 𝒪(n/ε). All previous approaches only support ε = ω(1/log n) 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%. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans-Peter Lehmann and Peter Sanders and Stefan Walzer and Jonatan Ziegler 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.109 urn:nbn:de:0030-drops-245780 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.109 eng https://creativecommons.org/licenses/by/4.0/legalcode