# Learning-augmented count-min sketches via Bayesian nonparametrics

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 74 references that are in the map.
- First posted on arXiv 8 Feb 2021.

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

- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Are Gibbs-type priors the most natural generalization of the Dirichlet process?](https://mlsanity.com/paper/1503.00163/) (2015)
- [(Learned) Frequency Estimation Algorithms under Zipfian Distribution](https://mlsanity.com/paper/1908.05198/) (2019)
- [Origins of power-law degree distribution in the heterogeneity of human activity in social networks](https://mlsanity.com/paper/1304.4523/) (2013)
- [The dynamics of correlated novelties](https://mlsanity.com/paper/1310.1953/) (2013)
- [Count-Min-Log sketch: Approximately counting with approximate counters](https://mlsanity.com/paper/1502.04885/) (2015)
- [Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions](https://mlsanity.com/paper/1811.04150/) (2018)
- [A Bayesian nonparametric approach to count-min sketch under power-law data streams](https://mlsanity.com/paper/2102.03743/) (2021)

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

- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Bayesian nonparametric estimation of coverage probabilities and distinct counts from sketched data](https://mlsanity.com/paper/2209.02135/) (2022)

## Abstract (arXiv)

The count-min sketch (CMS) is a time and memory efficient randomized data structure that provides estimates of tokens' frequencies in a data stream of tokens, i.e. point queries, based on random hashed data. A learning-augmented version of the CMS, referred to as CMS-DP, has been proposed by Cai, Mitzenmacher and Adams (textitNeurIPS 2018), and it relies on Bayesian nonparametric (BNP) modeling of the data stream of tokens via a Dirichlet process (DP) prior, with estimates of a point query being obtained as suitable mean functionals of the posterior distribution of the point query, given the hashed data. While the CMS-DP has proved to improve on some aspects of CMS, it has the major drawback of arising from a ``constructive" proof that builds upon arguments tailored to the DP prior, namely arguments that are not usable for other nonparametric priors. In this paper, we present a ``Bayesian" proof of the CMS-DP that has the main advantage of building upon arguments that are usable, in principle, within a broad class of nonparametric priors arising from normalized completely random measures. This result leads to develop a novel learning-augmented CMS under power-law data streams, referred to as CMS-PYP, which relies on BNP modeling of the data stream of tokens via a Pitman-Yor process (PYP) prior. Under this more general framework, we apply the arguments of the ``Bayesian" proof of the CMS-DP, suitably adapted to the PYP prior, in order to compute the posterior distribution of a point query, given the hashed data. Applications to synthetic data and real textual data show that the CMS-PYP outperforms the CMS and the CMS-DP in estimating low-frequency tokens, which are known to be of critical interest in textual data, and it is competitive with respect to a variation of the CMS designed for low-frequency tokens. An extension of our BNP approach to more general queries is also discussed.