Title: Sublinear-time Heavy Hitters with Universal Guarantees
Speaker: Martin J. Strauss, Michigan/Princeton
Date: Wednesday, September 27, 2006 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In the heavy hitters problem, the goal is to track the most frequent items in a changing collection, using little space. Over the last decade, a number of algorithms have been proposed for this problem. We present the first algorithms that simultaneously satisfy three important criteria: (i) the number of measurements is optimal, up to log factors (ii) the reconstruction time is polynomial in the number of heavy hitters and polylogarithmic in the universe size (iii) a single set of measurements (constructed randomly) works for all frequency vectors.
The talk is based on two papers. One is available as http://arxiv.org/abs/cs.DS/0608079 and the other is in progress.
Joint work with Anna Gilbert, Joel Tropp, and Roman Vershynin