# A Bayesian nonparametric approach to count-min sketch under power-law data streams

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 38 references that are in the map.
- First posted on arXiv 7 Feb 2021.

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

- [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)
- [Count-Min-Log sketch: Approximately counting with approximate counters](https://mlsanity.com/paper/1502.04885/) (2015)
- [Frequency of Frequencies Distributions and Size Dependent Exchangeable Random Partitions](https://mlsanity.com/paper/1608.00264/) (2016)

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

- [Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries](https://mlsanity.com/paper/2211.04612/) (2022)
- [Conformal Frequency Estimation with Sketched Data](https://mlsanity.com/paper/2204.04270/) (2022)
- [Learning-augmented count-min sketches via Bayesian nonparametrics](https://mlsanity.com/paper/2102.04462/) (2021)

## Abstract (arXiv)

The count-min sketch (CMS) is a randomized data structure that provides estimates of tokens' frequencies in a large data stream using a compressed representation of the data by random hashing. In this paper, we rely on a recent Bayesian nonparametric (BNP) view on the CMS to develop a novel learning-augmented CMS under power-law data streams. We assume that tokens in the stream are drawn from an unknown discrete distribution, which is endowed with a normalized inverse Gaussian process (NIGP) prior. Then, using distributional properties of the NIGP, we compute the posterior distribution of a token's frequency in the stream, given the hashed data, and in turn corresponding BNP estimates. Applications to synthetic and real data show that our approach achieves a remarkable performance in the estimation of low-frequency tokens. This is known to be a desirable feature in the context of natural language processing, where it is indeed common in the context of the power-law behaviour of the data.