2026-07-27T22:31:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11217 2024-03-06T10:47:43Z ddc:004 open_access

Tracking the l_2 Norm with Constant Update Time Chou, Chi-Ning Lei, Zhixian Nakkiran, Preetum Streaming algorithms Sketching algorithms Tracking CountSketch The l_2 tracking problem is the task of obtaining a streaming algorithm that, given access to a stream of items a_1,a_2,a_3,... from a universe [n], outputs at each time t an estimate to the l_2 norm of the frequency vector f^{(t)}in R^n (where f^{(t)}_i is the number of occurrences of item i in the stream up to time t). The previous work [Braverman-Chestnut-Ivkin-Nelson-Wang-Woodruff, PODS 2017] gave a streaming algorithm with (the optimal) space using O(epsilon^{-2}log(1/delta)) words and O(epsilon^{-2}log(1/delta)) update time to obtain an epsilon-accurate estimate with probability at least 1-delta. We give the first algorithm that achieves update time of O(log 1/delta) which is independent of the accuracy parameter epsilon, together with the nearly optimal space using O(epsilon^{-2}log(1/delta)) words. Our algorithm is obtained using the Count Sketch of [Charilkar-Chen-Farach-Colton, ICALP 2002]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chi-Ning Chou and Zhixian Lei and Preetum Nakkiran 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.2 urn:nbn:de:0030-drops-112175 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.2 eng https://creativecommons.org/licenses/by/3.0/legalcode