Hacker News Reader

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

View on HN

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.

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 :-)

Reply on news.ycombinator.com