Two-Stack Sliding-Window Aggregation

An algorithm for maintaining a running aggregate over a sliding window using two stacks is explained, offering amortized O(1) performance for any associative combine operation, not just invertible ones like sums. The technique generalizes to minimum, quantiles, approximate unique counts (HyperLogLog), and more by abstracting aggregation into empty, unit, combine, and finalize functions. The author traces the algorithm's folklore origins to a 2011 Stack Overflow post crediting a 2001 lecture on amortized two-stack FIFO queues, walks through a worked example summing a window of four elements, and explains why the approach also mitigates floating-point error accumulation since each aggregate only ever combines values currently inside the window.

Nguồn: https://orlp.net/blog/two-stack-sliding-window-aggregation. 8 Sync News chỉ tóm tắt và dẫn link; bản quyền nội dung thuộc tác giả và nguồn gốc.