2016/04/05 by Larsen, Kasper Green, Nelson, Jelani, Nguyen, Huy L. +1 · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1604.01357
In turnstile ℓp ε-heavy hitters, one maintains a high-dimensional x∈ℝn subject to update(i,Δ) causing xi← xi + Δ, where i∈[n], Δ∈ℝ. Upon receiving a query, the goal is to report a small list L⊂[n], |L| = O(1/εp), containing every "heavy hitter" i∈[n] with |xi| ≥ ε ‖x_1/εp‖p, where x_k 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(ε-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(ε-1log2 n), worse update time O(log2 n), but much better query time O(ε-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(ε-plog n) space, O(log n) update time, and fast O(ε-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.