*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
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
