Faster update time for turnstile streaming algorithms

Josh Alman, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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 1. partitions the coordinates into k < logo(1) n buckets using a c-wise independent hash function for constant c, 2. maintains the sum of coordinates for each bucket. Moreover, if arbitrary word operations are allowed, the update time can be further improved to O(log0.187 n), where 0.187 ≈ ω/2 − 1. Our update algorithm is adaptive, and it circumvents the non-adaptive cell-probe lower bounds for turnstile streaming algorithms by Larsen, Nelson and Nguyên (STOC'15). On the other hand, our result also shows that proving unconditional cell-probe lower bound for the update time seems very difficult, even if the space is restricted to be (nearly) the optimum. If ω = 2, the cell-probe update time of our algorithm would be logo(1) n. Hence, proving any higher lower bound would imply ω > 2.

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages1803-1813
Number of pages11
ISBN (Electronic)9781611975994
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/TerritoryUnited States
CitySalt Lake City
Period1/5/201/8/20

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Faster update time for turnstile streaming algorithms'. Together they form a unique fingerprint.

Cite this