Key Compression Limits for $k$-Minimum Value Sketches

Charlie Dickens, Eric Bax, Alexander Saydakov

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…