Joint work with Anna Gilbert, Joel Tropp, and Roman Vershynin
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.