Rendered at 14:22:19 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
mlochbaum 1 days ago [-]
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.
In some other words: cut your data in chunks of W length, build up all the forward and backwards partial sums for these chunks (for chunk [1:10] these are 1,1+2,1+2+3.., 10,10+9,10+9+8,..) and if you need a rolling sum somewhere just add the 2 corresponding partial sums. (This needs commutativity.)
This gives you C*n 'amortized' runtime, where 'amortized' means that it is C*n for a whole, big dataset independent of W. But there is an additional O(W) work needed to be done after every W-th element when you build up all the backwards sums.
I like it!
bradrn 1 days ago [-]
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.)
tinco 1 days ago [-]
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.
orlp 1 days ago [-]
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.
tinco 1 days ago [-]
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.
orlp 1 days ago [-]
> If you push, then pop, you should have the same data as you started with.
That's the case for a LIFO queue, but not a FIFO queue. Both commonly use the push/pop nomenclature.
dataflow 22 hours ago [-]
I would say that's not common but in fact I don't think I've ever seen both push() & pop() be used to refer to those operations on FIFO queues in any language. (And LIFO is a stack, the exact opposite of a queue.)
The terminology I've seen people use for FIFO instead is enqueue() and dequeue(). Or push_front(), pop_back(). Etc.
tinco 1 days ago [-]
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.
teiferer 1 days ago [-]
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.
Maybe use popleft?
Lichtso 22 hours ago [-]
If I am not mistaken a weighed fold / reduction [0] over a sliding window (kernel) is a convolution [1], right?
While the algorithm presented here is sequential, this smells like it could be done in parallel.
In fact the "cum_aggs" stack is a prefix scan [2].
For the sum of values (and by extension also the average), if you have the input prefix scanned (which can be done in parallel) then you can answer any (yes any, dynamic size, not fixed size window) subslice reduction in constant time.
Hm that's clever. You're basically taking the classic "queue using two stacks" algorithm but then replacing each stack with a min-stack (like in that leetcode problem where each element also tracks the aggregate of all elements below it) to get a "min queue".
And then unlike the usual monotone queue for sliding max/min, this works for any monoid since you're never comparing two elements.
armcat 1 days ago [-]
This is very cool, I can see a big use case on this for streaming analytics and anomaly detection. So if I get this right, you get:
- 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
orlp 1 days ago [-]
That's right, and one more property I consider very important for numerical stability:
- 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.
Sesse__ 23 hours ago [-]
I wish I knew about this algorithm when I worked in databases; it would be well-suited for window functions (even over floats for most users). Now I think I've seen it described two or three different places :-)
ncruces 1 days ago [-]
This is very cool.
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).
ktimespi 1 days ago [-]
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!!!
Would be nice to have some example code how the class is intended to be used
somat 20 hours ago [-]
I was having a bit of trouble understanding the specifics of how to use it as well so while trying to replicate the sum example I ended up with this. but the whole thing is so clunky I am sure I am holding it wrong.
def example_sum():
def sum_empty():
return 0
def sum_unit(value):
return value
def sum_combine(agg_a, agg_b):
return agg_a + agg_b
def sum_finalize(agg):
return agg
sum_agg = two_stack_agg(sum_empty, sum_unit, sum_combine, sum_finalize)
w_size = 4
entry_values = list(range(1, 11) )
trim_flag = False
i = 0
print(agg_sum.eval(), agg_sum.cum_aggs, agg_sum.values)
agg_sum.push(entry_values[i])
i += 1
while agg_sum.len() > 0:
if i < len(entry_values):
agg_sum.push(entry_values[i])
i += 1
if trim_flag:
agg_sum.pop()
elif agg_sum.len() >= w_size:
trim_flag = True
print(agg_sum.eval(), agg_sum.cum_aggs, agg_sum.values)
So a four window aggregate you push values and pop it when greater than the window size. I used the length(being the len of values + len cum_agg ) to measure the window size, but you could just count.
Most of the clunk was to get the same full fill/drain behavior as the example, probably unneeded on real data. The rest of the clunk is because I tend to write simple clunky python. and I stored the provided agg functions in the agg class.
ashkankiani 21 hours ago [-]
For the first sliding window, if all you need is the sum and your operator is invertible, you don't even need the double ended queue at all. You just need to know the Nth value that you need to invert when applying. So just keep track of the count and once you have N things, you can start yielding the Nth guy. That's literally 3 values to store.
teiferer 18 hours ago [-]
Could you elaborate? What do you do after having done this once? Where does the N-1th value come from if you didn't save it?
ashkankiani 6 hours ago [-]
Nope, you're right, I was wrong. You need the queue. This is a good reminder that:
- I should stop posting late at night when my ability to think is severely impacted
- I'm remembering this is not the first time I've made this mistake before with this particular algorithm, lol. I wonder what it is about it that leaves a hole in my reasoning/imagination.
aslushnikov 1 days ago [-]
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.
Thank you for sharing!
repiret 23 hours ago [-]
I discovered this algorithm a month ago or so, and have been telling everyone I can about it. I think it’s so damn cool.
My present Rust implementation can keep a sliding window sum of f32 at 300M/s.
teiferer 1 days ago [-]
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?
orlp 1 days ago [-]
`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!
This gives you C*n 'amortized' runtime, where 'amortized' means that it is C*n for a whole, big dataset independent of W. But there is an additional O(W) work needed to be done after every W-th element when you build up all the backwards sums.
I like it!
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.
The terminology I've seen people use for FIFO instead is enqueue() and dequeue(). Or push_front(), pop_back(). Etc.
Maybe use popleft?
While the algorithm presented here is sequential, this smells like it could be done in parallel.
In fact the "cum_aggs" stack is a prefix scan [2].
For the sum of values (and by extension also the average), if you have the input prefix scanned (which can be done in parallel) then you can answer any (yes any, dynamic size, not fixed size window) subslice reduction in constant time.
[0]: https://en.wikipedia.org/wiki/Fold_(higher-order_function) [1]: https://en.wikipedia.org/wiki/Convolution [2]: https://en.wikipedia.org/wiki/Prefix_sum
And then unlike the usual monotone queue for sliding max/min, this works for any monoid since you're never comparing two elements.
- 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.
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).
Most of the clunk was to get the same full fill/drain behavior as the example, probably unneeded on real data. The rest of the clunk is because I tend to write simple clunky python. and I stored the provided agg functions in the agg class.
- I should stop posting late at night when my ability to think is severely impacted
- I'm remembering this is not the first time I've made this mistake before with this particular algorithm, lol. I wonder what it is about it that leaves a hole in my reasoning/imagination.
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!
My present Rust implementation can keep a sliding window sum of f32 at 300M/s.
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.