Colloquium Details
The Heavy Hitter Problem in the Turnstile Streaming Model
| Author: | Yi Li Harvard University |
|---|---|
| Date: | February 24, 2015 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
In the turnstile model of data streams, an underlying vector x in R^n is presented as a long sequence of positive and negative updates to its coordinates. A randomized algorithm seeks to approximate a function f(x) with constant probability while only making a single pass over this sequence of updates and using a small amount of space. I shall primarily talk about the heavy hitter/space recovery problem, that is, f(x) returns the k largest coordinates (in absolute value) of x. Then I shall discuss, at a high level, the characterization of algorithms for general data stream problems.
Biography
Yi Li received his PhD from University of Michigan, Ann Arbor in 2013. Afterwards, he was a research fellow at the Simons Institute for the Theory of Computing with the ‘Foundations of Big Data Analysis’ program and then a postdoctoral researcher at Max-Planck Institute for Informatics in Germany. He is currently a postdoctoral fellow at Harvard University.