This repo contains reference implementations of many different sliding window aggregation algorithms.
All of these algorithms require operators that are associative. We classify the algorithms in two groups: those that require data to arrive in-order, and those that allow data to arrive out-of-order. We refer to the algorithms that require data to arrive in-order as FIFO algorithms, as they assume first-in, first-out semantics. We refer to algorithms that tolerate disordered data as general algorithms.
The algorithmic complexity of the algorithms is with respect to the size of the window.
A tutorial and encyclopedia article provide more background on sliding window aggregation algorithms.
- DABA and DABA Lite are worst-case O(1). The reference paper for DABA is Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time.
- FlatFIT and DynamicFlatFIT are average-case O(1) and worst-case O(n). The reference paper for FlatFIT is FlatFIT: Accelerated Incremental Sliding-Window Aggregation For Real-Time Analytics. Dynamic FlatFIT is an adaptation of FlatFIT that allows window resizing.
- IOA is the Imperative Okasaki Aggregator and it is worst-case O(1). It is based on Chris Okasaki's real time queues. The reference paper for IOA is Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time.
- Two-Stacks and Two-Stacks Lite are average-case O(1) and worst-case O(n). Two-Stacks was originally described by Jon Skeet on Stack Overflow.
- FiBA is the Finger B-Tree Aggregator and it is average-case O(log d) where d is the distance the newly arrived item is from being in-order, and worst-case O(log n). For in-order data, this reduces to average-case O(1) and worst-case O(log n). The reference paper for FiBA is Optimal and General Out-of-Order Sliding-Window Aggregation.
- Reactive is worst-case O(log n). The reference paper is General Incremental Sliding-Window Aggregation.