2 citations · 4 across the 8 of their papers we have counts for
13 papers
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…
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.…
ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
A minimal perfect hash function (MPHF) maps a set of keys to the first integers without collisions. There is a lower bound of bits of space needed…
Sliding Block Hashing (Slick) -- Basic Algorithmic Ideas
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
We present {\bf Sli}ding Blo{\bf ck} Hashing (Slick), a simple hash table data structure that combines high performance with very good space efficiency. This preliminary report out…
Learned Monotone Minimal Perfect Hashing
Paolo Ferragina, Hans-Peter Lehmann, Peter Sanders +1
A Monotone Minimal Perfect Hash Function (MMPHF) constructed on a set S of keys is a function that maps each key in S to its rank. On keys not in S, the function returns an arbitra…
High Performance Construction of RecSplit Based Minimal Perfect Hash Functions
Dominik Bez, Florian Kurpicz, Hans-Peter Lehmann +1
A minimal perfect hash function (MPHF) bijectively maps a set S of objects to the first |S| integers. It can be used as a building block in databases and data compression. RecSplit…
SicHash -- Small Irregular Cuckoo Tables for Perfect Hashing
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
A Perfect Hash Function (PHF) is a hash function that has no collisions on a given input set. PHFs can be used for space efficient storage of data in an array, or for determining a…
PaCHash: Packed and Compressed Hash Tables
Florian Kurpicz, Hans-Peter Lehmann, Peter Sanders
We introduce PaCHash, a hash table that stores its objects contiguously in an array without intervening space, even if the objects have variable size. In particular, each object ca…
Weighted Random Sampling on GPUs
Hans-Peter Lehmann, Lorenz Hübschle-Schneider, Peter Sanders
An alias table is a data structure that allows for efficiently drawing weighted random samples in constant time and can be constructed in linear time. The PSA algorithm by Hübschle…