2026-08-17T21:14:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6024 2024-03-06T10:37:29Z ddc:004 open_access

Efficient Summing over Sliding Windows Ben Basat, Ran Einziger, Gil Friedman, Roy Kassner, Yaron Streaming Statistics Lower Bounds This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of Omega(1/epsilon + log(W)) memory bits for Wepsilon-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/epsilon + log(W)) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0, 1, ..., R}, is addressed. The paper shows that approximating the sum within an additive error of RW epsilon can also be done using Theta(1/epsilon + log(W)) bits for epsilon = Omega(1/W). For epsilon = o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B = Theta(W*log(1/(W*epsilon))) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Ben Basat and Gil Einziger and Roy Friedman and Yaron Kassner 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.11 urn:nbn:de:0030-drops-60241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode