Key Compression Limits for $k$-Minimum Value Sketches
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912014731837440 |
|---|---|
| author | Dickens, Charlie Bax, Eric Saydakov, Alexander |
| author_facet | Dickens, Charlie Bax, Eric Saydakov, Alexander |
| contents | 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(\log n)$ bits per key in expected storage savings, where $n$ is the number of unique values in the data set. We also show that $O(\log n)$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02852 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Key Compression Limits for $k$-Minimum Value Sketches Dickens, Charlie Bax, Eric Saydakov, Alexander Data Structures and Algorithms Information Theory 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(\log n)$ bits per key in expected storage savings, where $n$ is the number of unique values in the data set. We also show that $O(\log n)$ 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. |
| title | Key Compression Limits for $k$-Minimum Value Sketches |
| topic | Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2409.02852 |