David Woodruff - IBM
Tuesday, June 7, 2016
Klaus Conference Room 2100 - 2:00 pm 

Title:
An Optimal Algorithm for Finding L2 Heavy Hitters

Abstract:
We consider the problem of finding the most frequent items in a stream of items from a universe of size n. Namely, we consider returning all l_2-heavy hitters, i.e., those items j for which f_j >= eps sqrt{F_2}, where f_j is the number of occurrences of item j, and F_2 = sum_i f_i^2 is the second moment of the stream. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which solves this using log^2 n bits of space (for constant eps). The only known lower bound is log n bits. Using Gaussian processes, we show it is possible to achieve an optimal log n bits of space. Our technique resolves a number of other questions in data streams.

Based on work with Vladimir Braverman, Stephen Chestnut, and Nikita Ivkin (STOC '16) and work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Jelani Nelson, and Zhengyu Wang.

Host: Santosh Vempala