3 papers
cs.DS2024
Hashing for Sampling-Based Estimation
Anders Aamand, Ioana O. Bercea, Jakob Bæk Tejs Houen +2
Hash-based sampling and estimation are common themes in computing. Using hashing for sampling gives us the coordination needed to compare samples from different sets. Hashing is al…
cs.DS2022
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…
cs.DS2022
Understanding the Moments of Tabulation Hashing via Chaoses
Jakob Bæk Tejs Houen, Mikkel Thorup
Simple tabulation hashing dates back to Zobrist in 1970 and is defined as follows: Each key is viewed as characters from some alphabet , we have fully random hash functi…