# BPTree: an ℓ2 heavy hitters algorithm using constant memory

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

## Key facts

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

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

- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)
- [Efficient Training of Language Models with Compact and Consistent Next Token Distributions](https://mlsanity.com/paper/2407.02819/) (2024)

## Abstract (arXiv)

The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list i1,i2,ldots,im∈[n] and the goal is to identify the items among [n] that appear frequently in the list. In sub-polynomial space, the strongest guarantee available is the ℓ2 guarantee, which requires finding all items that occur at least ε|f|2 times in the stream, where the vector f∈ℝn is the count histogram of the stream with ith coordinate equal to the number of times~i appears fi:=#j∈[m]:ij=i. The first algorithm to achieve the ℓ2 guarantee was the CountSketch of [CCF04], which requires O(ε-2log n) words of memory and O(log n) update time and is known to be space-optimal if the stream allows for deletions. The recent work of [BCIW16] gave an improved algorithm for insertion-only streams, using only O(ε-2logε-1loglog n) words of memory. In this work, we give an algorithm bptree for ℓ2 heavy hitters in insertion-only streams that achieves O(ε-2logε-1) words of memory and O(logε-1) update time, which is the optimal dependence on n and m. In addition, we describe an algorithm for tracking |f|2 at all times with O(ε-2) memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.