Revisiting Optimal Window Aggregation in Data Streams: The Prefix-Sum Approach

The article presents a simple yet optimal approach to compute aggregates of window queries over data streams. The proposal is built as a fully-fledged pipeline of operators that are literal transcripts of mathematical definitions. Main features are an application of the prefix sums and a well-founded un-/slicing technique. The overall process is linear in the number of events and windows, and it takes quasi-constant space for a mix of periodic windows, still applicable to multiple deterministic window queries. The limitations are twofold: the events come in-order and the aggregation function is a left-cancellative monoid.