Jelani Nelson
BPTree: an l_2 heavy hitters algorithm using constant memory

Abstract: In the 'frequent items' problem one sees a sequence of items
in a stream (e.g. a stream of words coming into a search query engine
like Google) and wants to report a small list of items containing all
frequent items. We would like algorithms for this problem that use
memory substantially sublinear in the length of the stream.

In this talk we describe a new state-of-the-art solution to this
problem, called the "BPTree". We make use of chaining methods to
control the suprema of Rademacher processes to develop this new
algorithm which has provably near-optimal memory consumption for the
"l_2" heavy hitters problem, improving upon the CountSieve and
CountSketch from previous work.

Based on joint work with Vladimir Braverman, Stephen Chestnut, Nikita
Ivkin, Zhengyu Wang, and David P. Woodruff