23 citations · 23 across the 3 of their papers we have counts for
9 papers · 1 filter
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…
Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold
Stefan Walzer
Most hash tables have an insertion time of , possibly qualified as expected and/or amortised. While insertions into cuckoo hash tables indeed seem to take expected tim…
Ribbon filter: practically smaller than Bloom and Xor
Peter C. Dillinger, Stefan Walzer
Filter data structures over-approximate a set of hashable keys, i.e. set membership queries may incorrectly come out positive. A filter with false positive rate is kn…
Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures
Stefan Walzer
In multiple-choice data structures each element in a set of keys is associated with a random set of buckets with capacity by hash fun…
Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
Martin Dietzfelbinger, Stefan Walzer
In this paper we identify a new class of sparse near-quadratic random Boolean matrices that have full row rank over with high probability and can be transfor…