Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time
Kanat Tangwongsan, Martin J. Hirzel, Scott Schneider · 2017
Sliding-window aggregation is a widely-used approach for extracting insights from the most recent portion of a data stream. The aggregations of interest can usually be cast as binary operators that are associative, but they are not necessarily commutative nor invertible. Non-invertible operators, however, are difficult to support efficiently. The best published algorithms require O(log n) aggregation steps per window operation, where n is the sliding-window size at that point. For a FIFO window, this can be improved to O(1) on average by using two aggregation stacks.