# Beating CountSketch for Heavy Hitters in Insertion Streams

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

## Key facts

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

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

- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

Given a stream p1, ldots, pm of items from a universe U, which, without loss of generality we identify with the set of integers 1, 2, ldots, n, we consider the problem of returning all ℓ2-heavy hitters, i.e., those items j for which fj ≥ ε √F2, where fj is the number of occurrences of item j in the stream, and F2 = sumi ∈ [n] fi2. Such a guarantee is considerably stronger than the ℓ1-guarantee, which finds those j for which fj ≥ ε m. In 2002, Charikar, Chen, and Farach-Colton suggested the sf CountSketch data structure, which finds all such j using Theta(log2 n) bits of space (for constant ε > 0). The only known lower bound is Omega(log n) bits of space, which comes from the need to specify the identities of the items found. In this paper we show it is possible to achieve O(log n log log n) bits of space for this problem. Our techniques, based on Gaussian processes, lead to a number of other new results for data streams, including (1) The first algorithm for estimating F2 simultaneously at all points in a stream using only O(log nloglog n) bits of space, improving a natural union bound and the algorithm of Huang, Tai, and Yi (2014). (2) A way to estimate the ℓ∞ norm of a stream up to additive error ε √F2 with O(log nloglog n) bits of space, resolving Open Question 3 from the IITK 2006 list for insertion only streams.