DIMACS Theoretical Computer Science Seminar

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


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