Post

Ragnar {Groot Koerkamp}
@curiouscoding.nl

My secret 4th ALGO paper is out! We show a tight space lower on non-minimal k-perfect hash functions, generalize PtrHash into a non-minimal k-PHF, and then use it to develop a hash set implementation that is up to 1.6x faster than other hash sets! With Stefan {Hermann, Walzer} and Peter Sanders

arXiv cs.DS Data Structures and Algorithms@csds-bot.bsky.social

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer: Non-minimal k-perfect hashing: Tight lower bounds and an application to fast static hash tables https://arxiv.org/abs/2607.07257 https://arxiv.org/pdf/2607.07257 https://arxiv.org/html/2607.07257

8 reposts16 likes

Ragnar {Groot Koerkamp}
@curiouscoding.nl

Also, I should mention how nicely theory and practice come together here. The practical application very much needed the theoretical space lower bound that Stefan Walzer and Stefan Hermann proved, so that we can target 1.5x that as a default space usage, rather than just guessing.

Ragnar {Groot Koerkamp}
@curiouscoding.nl

Basically: given a set of keys, we can use a 1-PHF to map the keys to distinct slots in an array. Then store the key itself in that slot to have a single-cache-miss hash set. Our k-PHF hash set variant maps e.g. k=8 64-bit keys to a cache line, and then uses SIMD instructions to check if it's there

Ragnar {Groot Koerkamp}
@curiouscoding.nl

So now, a non-minimal 8-PHF suffices, which only needs 0.08 bits/key at load factor 80%, compared to 0.86 bits/key for k=1 at load factor 80% or 1.44 bits/key for k=1 and a minimal PHF with load factor 1. Since it's 10x smaller, it fits in a lower cache and supports faster queries or larger inputs.

Ragnar {Groot Koerkamp}
@curiouscoding.nl

The main k-PHF-set speedup figure, with our results in blue. On my laptop (top row), the k-PHF allows throughput very close to the maximal memory throughput up to n=2^28, whereas previous methods only reached that up to 2^24. Also, it performs equally well for both positive and negative queries.