As you suspected, there's some older literature on this, from the 1990s in image processing. There it's not based on stacks or queues but on splitting the output into blocks with the same size as the (constant-length) window. It's sometimes called the van Herk/Gil-Werman algorithm after two sets of independent discoverers; of the two papers I prefer "Computing 2-D Min, Median, and Max Filters" by Gil and Werman which spends just a paragraph on the 1-D windowed operation in section II.
I just want to comment that, quite aside from the content (which is very interesting) I particularly enjoy the design of this website — it’s very clean and balanced and easy to read. (In fact I first encountered it a while ago, noted this at the time, then forgot the URL. I’m glad to have come across it again.)
Very cool, might I suggest you rename your `pop` function to `shift` (or if you like ugly names `popleft`)? Popping windows isn't really a thing, it made me double take on the code.
I don't like `shift` as a name because it might give the impression the entire window shifts. Push increases the window size by one and pop decreases the window size by one (evicting the earliest pushed element).
In my mental model `shift` would move the entire window, it would be one push + one pop.
Ok, but shift is the commonly used name for that operation, and pop commonly does something else than what you just described. If you could come up with a better word than shift that would be fine, but pop should be the inverse of push in my opinion. If you push, then pop, you should have the same data as you started with.
Ah I haven't seen that before. I must admit that I'm not in the literature side of things. Any time I've seen a queue in production it would use put/get or enqueue/dequeue and in Ruby scripts you'd use an array and use push/shift.
Unfortunately, pop means two different things then. For the python lists, it pops "from the right" but for TwoStackAgg it pops "from the left". That makes the code harder to grasp.
We're computing sliding window aggregations to detect regressions on a history of commits in Flakiness.io.
Our current algorithm is suboptimal, so we had to limit the "lookback": a test failure is marked as a regression iff it had a perfect history for the last 10 observed commits.
While the current approach works reasonably well, we had a few requests to make lookback larger/configurable, which we now might be able to do with this algorithm.
I was working on aggregations like this for a datalog research project and couldn't figure out a way to do it without recomputing the entire window. I love the way this exchanges space for compute, this is really cool!!!
What do you need self.values_agg for? It is only used for the aggregate of values not yet represented in cum_aggs if finalize is called. That value could just get computed right there on the fly.
Is it maybe for repeated finalize calls? To essentially re-use those computations?
`values` might be quite large (up to W), without `values_agg` getting the current window value would be O(W) rather than O(1).
Note that there isn't a `finalize` call, only an `eval`, which gives the current aggregate over the window. You typically use these sliding window functions in a way where you want to get the current value every time the window moves.
I don't know who first described this as a streaming version but I like the presentation at https://signalsmith-audio.co.uk/writing/2022/constant-time-p... . It is indeed too obscure considering how useful it is!
My present Rust implementation can keep a sliding window sum of f32 at 300M/s.
In my mental model `shift` would move the entire window, it would be one push + one pop.
That's the case for a LIFO queue, but not a FIFO queue. Both commonly use the push/pop nomenclature.
Maybe use popleft?
- Amortized O(1) work per window update
- O(1) aggregate queries, assuming a fixed cost merge operation
- O(W) memory for W buckets, with sketch size treated as fixed
- No need to recompute the entire window every second
- The aggregate only depends on the value currently in the window.
Most problems caused by NaNs/infinities/catastrophic cancellation/etc in sliding windows are covered by this property.
Our current algorithm is suboptimal, so we had to limit the "lookback": a test failure is marked as a regression iff it had a perfect history for the last 10 observed commits.
While the current approach works reasonably well, we had a few requests to make lookback larger/configurable, which we now might be able to do with this algorithm.
Thank you for sharing!
SQLite uses the "streaming" push/pop/eval API for windowed aggregates.
DuckDB implements "segment tree aggregation" by swapping "combine" for "pop".
This means I can offer an adapter that turns combinable aggregates into invertible aggregates, in amortized O(1).
Is it maybe for repeated finalize calls? To essentially re-use those computations?
Note that there isn't a `finalize` call, only an `eval`, which gives the current aggregate over the window. You typically use these sliding window functions in a way where you want to get the current value every time the window moves.