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

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.

1 repost1 like

No replies yet.