Two-Stack Sliding-Window Aggregation

2 comments

• tinco 44 minutes 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.
• armcat 10 minutes 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