The Two-Stack Trick That Solves Sliding-Window Aggregation for Almost Any Function
Two-Stack Sliding-Window Aggregation
Sliding-window aggregation is easy when your operation has an inverse, like integer sums. But for min, max, quantiles, or even floating-point sums, the naive approach fails—a single NaN can poison your results forever. This post explains the two-stack algorithm, a simple, amortized O(1) method that works for any associative aggregation. It also shows how the algorithm avoids error propagation from outliers, making it ideal for floating-point windows.
Each aggregate is strictly a combination of the elements in the window, and none outside the window. This means if your window contains a NaN or infinity (or some other outlier), that value only poisons the windows that contain it rather than the rest of your computation.