Sliding-Window Aggregation Algorithms

Sliding-window aggregation summarizes a collection of recent streaming data, capturing the most recent happenings as well as some history. Algorithms for this problem are required to maintain an aggregate value as new data items are inserted into the window when they arrive, and old data items are evicted from the window when they expire. Supporting this efficiently poses algorithmic challenges, especially for non-invertible aggregation functions such asmax—, for which there is no way to “subtract off” expiring items. This chapter provides a brief overview of this area of research and explores a number of sliding-window aggregation algorithms, including both simple and sophisticated algorithms. Real-world use cases are also given to showcase problem scenarios where sliding-window aggregation can be applicable.