Heavy hitters via cluster-preserving clustering

In turnstile ℓp varepsilon-heavy hitters, one maintains a high-dimensional x∈ℝn subject to textttupdate(i,Delta) causing xileftarrow xi + Delta, where i∈[n], Delta∈ℝ. Upon receiving a query, the goal is to report a small list Lsubset[n], |L| = O(1/varepsilonp), containing every "heavy hitter" i∈[n] with |xi| ≥ varepsilon |x_overline1/varepsilonp|p, where x_overlinek denotes the vector obtained by zeroing out the largest k entries of x in magnitude. For any p∈(0,2] the CountSketch solves ℓp heavy hitters using O(varepsilon-plog n) words of space with O(log n) update time, O(nlog n) query time to output L, and whose output after any query is correct with high probability (whp) 1 - 1/poly(n). Unfortunately the query time is very slow. To remedy this, the work [CM05] proposed for p=1 in the strict turnstile model, a whp correct algorithm achieving suboptimal space O(varepsilon-1log2 n), worse update time O(log2 n), but much better query time O(varepsilon-1poly(log n)). We show this tradeoff between space and update time versus query time is unnecessary. We provide a new algorithm, ExpanderSketch, which in the most general turnstile model achieves optimal O(varepsilon-plog n) space, O(log n) update time, and fast O(varepsilon-ppoly(log n)) query time, and whp correctness. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We then develop a "cluster-preserving clustering" algorithm, partitioning the graph into clusters without destroying any original cluster.