2016/03/02 by Vladimir Braverman, Braverman, Vladimir, Stephen R. Chestnut +9 · 4 citations
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1603.00759
openalex publication_date 2016/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list i1,i2,…,im∈[n] and the goal is to identify the items among [n] that appear frequently in the list. In sub-polynomial space, the strongest guarantee available is the ℓ2 guarantee, which requires finding all items that occur at least ε‖f‖2 times in the stream, where the vector f∈ℝn is the count histogram of the stream with ith coordinate equal to the number of times~i appears fi:=#\j∈[m]:ij=i\. The first algorithm to achieve the ℓ2 guarantee was the CountSketch of [CCF04], which requires O(ε-2log n) words of memory and O(log n) update time and is known to be space-optimal if the stream allows for deletions. The recent work of [BCIW16] gave an improved algorithm for insertion-only streams, using only O(ε-2logε-1loglog n) words of memory. In this work, we give an algorithm \bptree for ℓ2 heavy hitters in insertion-only streams that achieves O(ε-2logε-1) words of memory and O(logε-1) update time, which is the optimal dependence on n and m. In addition, we describe an algorithm for tracking ‖f‖2 at all times with O(ε-2) memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.