HN

Comments (22)

• mlochbaum
  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 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!
• ashkankiani
  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.
• Lichtso
  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.[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
• bradrn
  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.)
• Menu

  tinco
  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.
• Menu

  armcat
  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
• ktimespi
  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!!!
• aslushnikov
  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!
• MawKKe
  Would be nice to have some example code how the class is intended to be used
• repiret
  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.
• ncruces
  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).
• Menu

  teiferer
  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?
• arbor-group
  [flagged]
• ibraryunus
  [flagged]