Gil Einziger

This paper considers the problem of estimating the sum the last W elements of a stream of integers in { 0 , 1 , … , R}. Specifically, we study the memory requirements for computing a RWε-additive approximation for the window’s sum. We derive a lower bound of Wlog⌊12Wε+1⌋ bits when ε≤ 1 / 2 W and show a matching succinct algorithm that uses (1+o(1))(Wlog⌊12Wε+1⌋) bits. Next, we prove a (1 - o(1)) ε ^{- 1} / 2 bits lower bound when ε= ω(W ^{- 1} ) ∧ ε= o(log ^{- 1} W) and provide a succinct algorithm that requires (1 + o(1)) ε ^{- 1} / 2 bits. We show that when ε= Ω(log ^{- 1} W) any solution to the problem must consume at least (1 - o(1)) · (ε ^{- 1} / 2 + log W) bits, while our algorithm needs (1 + o(1)) · (ε ^{- 1} / 2 + 2 log W) bits. Finally, we show that our lower bounds generalize to randomized algorithms as well, while our algorithms are deterministic and can process elements and answer queries in O(1) worst-case time.