Imagine you're building a noise detector that needs to track the maximum decibel level over the last 30 seconds. As new data streams in, old data drops out. Simple, right? Well, if you're calculating a sum, it's easy: just add the new value and subtract the old one. But what if you're tracking a maximum, a minimum, or a quantile? You can't just 'subtract' a maximum value when it leaves the window. This is where the Two-Stack Sliding-Window Aggregation (SWAG) comes in.
The Problem with Non-Invertible Math
In the world of algorithms, some operations have an inverse (like addition and subtraction). Others—like max(), min(), or calculating unique counts—are non-invertible. Once the largest value in your window slides out of view, you can't mathematically 'undo' it to find the next highest value without re-scanning the entire window. For high-frequency data, re-scanning every time is a performance nightmare.
How the Two-Stack Magic Works
SWAG turns a queue (FIFO) into two stacks. One stack handles incoming data (push), and the other handles outgoing data (pop). The secret sauce is that each stack maintains a running aggregation of its own elements.
When the 'pop' stack is empty, the algorithm simply flips the 'push' stack into it, recalculating the aggregates along the way. Because this flip happens infrequently, the cost is spread out, resulting in an amortized O(1) time complexity. As long as your operation is associative (meaning the order of grouping doesn't matter), you can combine the summaries of both stacks to get the window's total aggregate instantly.
Why It Matters
Whether you're handling financial tick data or IoT sensor streams, SWAG provides a robust way to handle 'poison' values (like NaNs) and non-invertible operators without sacrificing speed. It transforms a potentially expensive O(N) scan into a lightning-fast constant-time lookup.
Sources
Media
