Perfect hash function awarded at ESA'25

Our consensus data structure makes it possible to store seeds for randomized data structures in a particularly space-efficient manner. As an application of Consensus, we present the world's most space-efficient perfect hash function. We have now received the Best Paper Award for the development of Consensus at the European Symposium on Algorithms (ESA'25) in Warsaw.

Many randomized data structures use the principle of trying out different seeds until an attempt is successful. If we have many such data structures, one classically stores the first working seed for each substructure. We show that this approach wastes storage space, even if the seeds are encoded optimally. Our new Consensus data structure combines the search for seeds directly with their storage. Consensus "blurs" where each individual seed is stored to both save space and make decoding more efficient.

To show the potential of the idea, we consider the application of minimal perfect hash functions. With Consensus-RecSplit we present the first minimal perfect hash function whose construction time only grows linearly in the inverse space overhead. We achieve a space overhead extremely close to the theoretical minimum, while the construction for larger space overheads is up to two orders of magnitude faster than all previous techniques.

ESA is one of the most important conferences for algorithms, this year with 115 accepted papers. We are pleased that our research convinced the reviewers. The paper "Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing" by Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, and Jonatan Ziegler is freely available as open access.