23 citations · 28 across the 13 of their papers we have counts for
18 papers
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…
What if we tried Less Power? -- Lessons from studying the power of choices in hashing-based data structures
Stefan Walzer
In the first part of this survey, we review how the power of two choices underlies space-efficient data structures like cuckoo hash tables. We'll find that the additional power aff…
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…
Optimal Uncoordinated Unique IDs
Peter C. Dillinger, Martín Farach-Colton, Guido Tagliavini +1
In the Uncoordinated Unique Identifiers Problem (UUIDP) there are independent instances of an algorithm that generates IDs from a universe , and…
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…
Simple Set Sketching
Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer
Imagine handling collisions in a hash table by storing, in each cell, the bit-wise exclusive-or of the set of keys hashing there. This appears to be a terrible idea: For keys…