The task of finding heavy hitters is one of the best known and well studied
problems in the area of data streams. In sub-polynomial space, the strongest
guarantee available is the $\ell_2$ guarantee, which requires finding all items
that occur at least $\varepsilon\|f\|_2$ times in the stream, where the $i$th
coordinate of the vector $f$ is the number of occurrences of $i$ in the stream.
The first algorithm to achieve the $\ell_2$ guarantee was the CountSketch of
[CCF04], which for constant $\varepsilon$ requires $O(\log 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(\log\log n)$ words of memory.
In this work, we give an algorithm "BPTree" for $\ell_2$ heavy hitters in
insertion-only streams that achieves $O(1)$ words of memory and $O(1)$ update
time for constant $\varepsilon$, which is optimal. In addition, we describe an
algorithm for tracking $\|f\|_2$ at all times with $O(1)$ 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.