Hashing for Sampling-Based Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910719922929664 |
|---|---|
| author | Aamand, Anders Bercea, Ioana O. Houen, Jakob Bæk Tejs Klausen, Jonas Thorup, Mikkel |
| author_facet | Aamand, Anders Bercea, Ioana O. Houen, Jakob Bæk Tejs Klausen, Jonas Thorup, Mikkel |
| contents | Hash-based sampling and estimation are common themes in computing. Using hashing for sampling gives us the coordination needed to compare samples from different sets. Hashing is also used when we want to count distinct elements. The quality of the estimator for, say, the Jaccard similarity between two sets, depends on the concentration of the number of sampled elements from their intersection. Often we want to compare one query set against many stored sets to find one of the most similar sets, so we need strong concentration and low error-probability. In this paper, we provide strong explicit concentration bounds for Tornado Tabulation hashing [Bercea, Beretta, Klausen, Houen, and Thorup, FOCS'23] which is a realistic constant time hashing scheme. Previous concentration bounds for fast hashing were off by orders of magnitude, in the sample size needed to guarantee the same concentration. The true power of our result appears when applied in the local uniformity framework by [Dahlgaard, Knudsen, Rotenberg, and Thorup, STOC'15]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19394 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hashing for Sampling-Based Estimation Aamand, Anders Bercea, Ioana O. Houen, Jakob Bæk Tejs Klausen, Jonas Thorup, Mikkel Data Structures and Algorithms Hash-based sampling and estimation are common themes in computing. Using hashing for sampling gives us the coordination needed to compare samples from different sets. Hashing is also used when we want to count distinct elements. The quality of the estimator for, say, the Jaccard similarity between two sets, depends on the concentration of the number of sampled elements from their intersection. Often we want to compare one query set against many stored sets to find one of the most similar sets, so we need strong concentration and low error-probability. In this paper, we provide strong explicit concentration bounds for Tornado Tabulation hashing [Bercea, Beretta, Klausen, Houen, and Thorup, FOCS'23] which is a realistic constant time hashing scheme. Previous concentration bounds for fast hashing were off by orders of magnitude, in the sample size needed to guarantee the same concentration. The true power of our result appears when applied in the local uniformity framework by [Dahlgaard, Knudsen, Rotenberg, and Thorup, STOC'15]. |
| title | Hashing for Sampling-Based Estimation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.19394 |