MADALGO Theory Seminar

MADALGO Seminar: Jelani Nelson (Harvard University): "Heavy hitters via cluster-preserving clustering"

2016.04.18 | Katrine Østerlund Rasmussen

Date Tue 19 Apr
Time 13:30 14:15
Location Nygaard-395

Heavy hitters via cluster-preserving clustering

Previously it was known that all l2 eps-heavy hitters could be found in the turnstile model in optimal O((1/eps^2) lg n) words of space with O(lg n) update time and very slow O(n lg n) query time with 1/poly(n) failure probability, via the CountSketch of Charikar, Chen and Farach-Colton. The query time could be improved drastically using the "dyadic trick" to O((1/eps^2) poly(lg n)), but the space and update time worsened to log^2 n to achieve such small failure probability. We show that the best of all worlds is possible: we give a new algorithm, ExpanderSketch, achieving O((1/eps^2) lg n) space, O(lg n) update time, and O((1/eps^2) poly(lg n)) query with 1/poly(n) failure probability. This is accomplished via a new reduction from the heavy hitters problem to a graph clustering problem of independent interest, which we solve using a new clustering algorithm CutCloseGrab which is guaranteed to find every single cluster regardless of the number of clusters or the comparative sizes between the cluster and the entire graph.

Joint work with Kasper Green Larsen, Huy L. Nguyen, and Mikkel Thorup.

Lecture / talk