# Frequency Estimation with One-Sided Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2021.

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

- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)

## Abstract (arXiv)

Frequency estimation is one of the most fundamental problems in streaming algorithms. Given a stream S of elements from some universe U=1 ldots n, the goal is to compute, in a single pass, a short sketch of S so that for any element i ∈ U, one can estimate the number xi of times i occurs in S based on the sketch alone. Two state of the art solutions to this problems are the Count-Min and Count-Sketch algorithms. The frequency estimator tildex produced by Count-Min, using O(1/varepsilon · log n) dimensions, guarantees that |tildex-x|∞ ≤ varepsilon |x|1 with high probability, and tildex ≥ x holds deterministically. Also, Count-Min works under the assumption that x ≥ 0. On the other hand, Count-Sketch, using O(1/varepsilon2 · log n) dimensions, guarantees that |tildex-x|∞ ≤ varepsilon |x|2 with high probability. A natural question is whether it is possible to design the best of both worlds sketching method, with error guarantees depending on the ℓ2 norm and space comparable to Count-Sketch, but (like Count-Min) also has the no-underestimation property. Our main set of results shows that the answer to the above question is negative. We show this in two incomparable computational models: linear sketching and streaming algorithms. We also study the complementary problem, where the sketch is required to not over-estimate, i.e., tildex ≤ x should hold always.