# Sharp Frequency Bounds for Sample-Based Queries

arXiv: https://arxiv.org/abs/2208.06753 · HTML: https://mlsanity.com/paper/2208.06753/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 14 references that are in the map.
- First posted on arXiv 14 Aug 2022.

## Built on by (most cited first, 1 of 1)

- [Early Stopping Based on Repeated Significance](https://mlsanity.com/paper/2408.00908/) (2024)

## Abstract (arXiv)

A data sketch algorithm scans a big data set, collecting a small amount of data -- the sketch, which can be used to statistically infer properties of the big data set. Some data sketch algorithms take a fixed-size random sample of a big data set, and use that sample to infer frequencies of items that meet various criteria in the big data set. This paper shows how to statistically infer probably approximately correct (PAC) bounds for those frequencies, efficiently, and precisely enough that the frequency bounds are either sharp or off by only one, which is the best possible result without exact computation.