Faster Update Time for Turnstile Streaming Algorithms
Josh Alman, Huacheng Yu · Society for Industrial and Applied Mathematics eBooks · 2019
In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that log n Count sketches or CountMin sketches with a constant number of columns (i.e., buckets) can be implicitly maintained in worst-case O(log0.582 n) update time using O(log n) words of space, on a standard word RAM with word-size w = Θ(log n). The exponent 0.582 ≈ 2ω/3 – 1, where ω is the current matrix multiplication exponent. Due to the numerous applications of linear sketches, our algorithm improves the update time for many streaming problems in turnstile streams, in the high success probability setting, without using more space, including ℓ2 norm estimation, ℓ2 heavy hitters, point query with ℓ1 or ℓ2 error, etc. Our algorithm generalizes, with the same update time and space, to maintaining log n linear sketches, where each sketch partitions the coordinates into k 2.