Improved concentration bounds for count-sketch. arXiv preprint arXiv:1207.5200

We present a refined analysis of the classic Count-Sketch streaming heavy hitters algo-rithm [CCF02]. Count-Sketch uses O(k log n) linear measurements of a vector x ∈ Rn to give an estimate x ̂ of x. The standard analysis shows that this estimate x ̂ satisfies ‖x̂−x‖2 ∞ < ‖x[k]‖22/k, where x [k] is the vector containing all but the largest k coordinates of x. Our main result is that most of the coordinates of x ̂ have substantially less error than this upper bound; namely, for any c < O(log n), we show that each coordinate i satisfies (x̂i − xi)2 < c log