Two-Stack Sliding-Window Aggregation

In the world of data aggregation, the objective is often to calculate a summary, such as the sum, minimum, or maximum, over a set of data points. This process commonly involves a sliding window, which is a fixed-size subset of the data that moves along the entire dataset. The challenge arises when the aggregation operation lacks an inverse, as is the case for most useful summaries like minimum, quantile, or approximate unique count.

One such algorithm was developed by the author six years ago for maintaining minimum and maximum values in a sliding window, but they now consider it obsolete due to the existence of a more efficient solution. The author discovered this algorithm while studying a more advanced paper titled "Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time" by Tangwongsan et al.

However, the paper's authors incorrectly attributed the "two-stack" algorithm to "adamax" from a 2011 Stack Overflow post, who in turn credited a 2001 lecture note by D. Sleator. The two-stack algorithm, simple yet elegant, has been generalized to work with arbitrary associative aggregation functions, including examples like a mean, approximate unique count, or floating-point sum.

The algorithm utilizes two stacks (values and cum_aggs), along with an additional aggregate (values_agg), which holds the cumulative aggregate of values. By draining values every w operations, the algorithm maintains a running aggregate and pushes partial cumulative aggregates onto cum_aggs, ensuring that the aggregate over the entire window can be obtained in constant time.

The memory usage of the algorithm is O(w), where w is the window size. Although floating-point addition does not meet the associative property requirement, the algorithm still proves useful due to its close resemblance to expected outcomes and the mitigation of error propagation through compensated summation methods. Additionally, the algorithm ensures that each aggregate is strictly a combination of elements within the window, preventing the poisoning of the computation by outliers such as NaN or infinity values.