2 citations · 5 across the 7 of their papers we have counts for
12 papers
Stuffed IBLTs: Optimal Linear Multiset Sketches
Jonas Klausen, Rasmus Pagh, Stefan Walzer
A \emph{linear sketch} is a randomized linear mapping of a vector to a lower dimensional sketch vector, designed to preserve relevant information about . We consider sketche…
Quadratic Probing Insertions Are Time
Yang Hu, William Kuszmaul, Jingxun Liang +3
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectur…
Non-Minimal -Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables
Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders +1
A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of keys to bins without collisions. Two natural generalizations are minimal -PHFs…
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood
Yang Hu, William Kuszmaul, Jingxun Liang +3
Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees rema…
Learned Static Function Data Structures
Stefan Hermann, Hans-Peter Lehmann, Giorgio Vinciguerra +1
We consider the task of constructing a data structure for associating a static set of keys with values, while allowing arbitrary output values for queries involving keys outside th…
Modern Minimal Perfect Hashing: A Survey
Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh +4
Given a set of keys, a perfect hash function for maps the keys in to the first integers without collisions. It may return an arbitrary result for any key…
Engineering Minimal k-Perfect Hash Functions
Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann +2
Given a set S of n keys, a k-perfect hash function (kPHF) is a data structure that maps the keys to the first m integers, where each output integer can be hit by at most k input ke…
Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer +1
Randomised algorithms often employ methods that can fail and that are retried with independent randomness until they succeed. Randomised data structures therefore often store indic…
PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding
Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri +2
A minimal perfect hash function (MPHF) maps a set of n keys to {1, ..., n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In t…
Better space-time-robustness trade-offs for set reconciliation
Djamal Belazzougui, Gregory Kucherov, Stefan Walzer
We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact sol…
The Probability to Hit Every Bin with a Linear Number of Balls
Stefan Walzer
Assume that balls are thrown independently and uniformly at random into bins. We consider the unlikely event that every bin receives at least one ball, showing that $\…
ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. There is a lower bound of n*log(e)=1.44n bits needed to represent an MPHF.…