# (Learned) Frequency Estimation Algorithms under Zipfian Distribution

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2019.

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

- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels](https://mlsanity.com/paper/2310.01655/) (2023)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries](https://mlsanity.com/paper/2211.04612/) (2022)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [A Bayesian nonparametric approach to count-min sketch under power-law data streams](https://mlsanity.com/paper/2102.03743/) (2021)
- [Learning-augmented count-min sketches via Bayesian nonparametrics](https://mlsanity.com/paper/2102.04462/) (2021)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)

## Abstract (arXiv)

beginabstract The frequencies of the elements in a data stream are an important statistical measure and the task of estimating them arises in many applications within data analysis and machine learning. Two of the most popular algorithms for this problem, Count-Min and Count-Sketch, are widely used in practice. In a recent work [Hsu et al., ICLR'19], it was shown empirically that augmenting Count-Min and Count-Sketch with a machine learning algorithm leads to a significant reduction of the estimation error. The experiments were complemented with an analysis of the expected error incurred by Count-Min (both the standard and the augmented version) when the input frequencies follow a Zipfian distribution. Although the authors established that the learned version of Count-Min has lower estimation error than its standard counterpart, their analysis of the standard Count-Min algorithm was not tight. Moreover, they provided no similar analysis for Count-Sketch. In this paper we resolve these problems. First, we provide a simple tight analysis of the expected error incurred by Count-Min. Second, we provide the first error bounds for both the standard and the augmented version of Count-Sketch. These bounds are nearly tight and again demonstrate an improved performance of the learned version of Count-Sketch. In addition to demonstrating tight gaps between the aforementioned algorithms, we believe that our bounds for the standard versions of Count-Min and Count-Sketch are of independent interest. In particular, it is a typical practice to set the number of hash functions in those algorithms to Theta (log n). In contrast, our results show that to minimize the expected error, the number of hash functions should be a constant, strictly greater than 1.