Two-Stack Sliding-Window Aggregation

This describes a simple, general algorithm for maintaining aggregates over a sliding window when the aggregation operator lacks an inverse (so naive deque subtraction won’t work). It generalizes a two-stack technique to any associative aggregation by exposing four functions: empty(), unit(x), combine(a,b) and finalize(a). Typical use cases include min/max, quantiles, approximate distinct counts (e.g., HyperLogLog), and means. The claim is that this two-stack construction is compact, uses O(w) memory for a window of size w, and achieves amortized O(1) work per element, making it practical and broadly applicable where inverse or exact incremental updates aren’t available.

Operationally it keeps a values stack plus a cumulative-aggregates stack and a running aggregate for values. push(x) appends x and updates the values aggregate; pop() lazily drains values into cum_aggs by building cumulative aggregates in reverse order when needed and then pops from cum_aggs; eval() combines the last cum_aggs entry with the values aggregate and finalizes the result. The method preserves operand order (no commutativity requirement), bounds per-element work amortizedly, and confines corruption (NaN/infinity or large floating-point errors) to only windows that actually contain bad inputs. Floating-point non-associativity is noted, but practical results are good and can be improved with compensated summation.