Ben Basat, Ran ;
Einziger, Gil ;
Friedman, Roy ;
Kassner, Yaron
Efficient Summing over Sliding Windows
Abstract
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 Wepsilonadditive 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) worstcase time.
BibTeX  Entry
@InProceedings{benbasat_et_al:LIPIcs:2016:6024,
author = {Ran Ben Basat and Gil Einziger and Roy Friedman and Yaron Kassner},
title = {{Efficient Summing over Sliding Windows}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {11:111:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770118},
ISSN = {18688969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6024},
URN = {urn:nbn:de:0030drops60241},
doi = {10.4230/LIPIcs.SWAT.2016.11},
annote = {Keywords: Streaming, Statistics, Lower Bounds}
}
22.06.2016
Keywords: 

Streaming, Statistics, Lower Bounds 
Seminar: 

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Issue date: 

2016 
Date of publication: 

22.06.2016 