Key Compression Limits For k-minimum Value Sketches

Dickens Charlie, Bax Eric, Saydakov Alexander. Arxiv 2024

[Paper]    
ARXIV Independent

The $k$-Minimum Values (\kmv) data sketch algorithm stores the $k$ least hash keys generated by hashing the items in a dataset. We show that compression based on ordering the keys and encoding successive differences can offer $O(logn)$ bits per key in expected storage savings, where $n$ is the number of unique values in the data set. We also show that $O(logn)$ expected bits saved per key is optimal for any form of compression for the $k$ least of $n$ random values – that the encoding method is near-optimal among all methods to encode a \kmv sketch. We present a practical method to perform that compression, show that it is computationally efficient, and demonstrate that its average savings in practice is within about five percent of the theoretical minimum based on entropy. We verify that our method outperforms off-the-shelf compression methods, and we demonstrate that it is practical, using real and synthetic data.

Similar Work

• On The Optimal Time/space Tradeoff For Hash Tables
• Recsplit Minimal Perfect Hashing Via Recursive Splitting
• Invertible Bloom Lookup Tables With Less Memory And Randomness
• Practical Data-dependent Metric Compression With Provable Guarantees