# Bayesian nonparametric estimation of coverage probabilities and distinct counts from sketched data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 86 references that are in the map.
- First posted on arXiv 5 Sep 2022.

## Builds on (most cited first, 8 of 8)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Efficient Private Statistics with Succinct Sketches](https://mlsanity.com/paper/1508.06110/) (2015)
- [On the Impossibility of Learning the Missing Mass](https://mlsanity.com/paper/1503.03613/) (2015)
- [Rediscovery of Good-Turing estimators via Bayesian nonparametrics](https://mlsanity.com/paper/1401.0303/) (2014)
- [Learning-augmented count-min sketches via Bayesian nonparametrics](https://mlsanity.com/paper/2102.04462/) (2021)
- [Bayesian nonparametric inference for discovery probabilities: credible intervals and large sample asymptotics](https://mlsanity.com/paper/1506.04915/) (2015)

## Abstract (arXiv)

The estimation of coverage probabilities, and in particular of the missing mass, is a classical statistical problem with applications in numerous scientific fields. In this paper, we study this problem in relation to randomized data compression, or sketching. This is a novel but practically relevant perspective, and it refers to situations in which coverage probabilities must be estimated based on a compressed and imperfect summary, or sketch, of the true data, because neither the full data nor the empirical frequencies of distinct symbols can be observed directly. Our contribution is a Bayesian nonparametric methodology to estimate coverage probabilities from data sketched through random hashing, which also solves the challenging problems of recovering the numbers of distinct counts in the true data and of distinct counts with a specified empirical frequency of interest. The proposed Bayesian estimators are shown to be easily applicable to large-scale analyses in combination with a Dirichlet process prior, although they involve some open computational challenges under the more general Pitman-Yor process prior. The empirical effectiveness of our methodology is demonstrated through numerical experiments and applications to real data sets of Covid DNA sequences, classic English literature, and IP addresses.