Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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

 help



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.

reply


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




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: