Sliding Window Aggregators

This repo contains reference implementations of 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 the algorithms that tolerate disordered data as general algorithms.

The algorithmic complexity of the algorithms is with respect to the size of the window, n.

A tutorial and encyclopedia article provide more background on sliding window aggregation algorithms.

DABA

• full name: De-Amortized Banker's Aggregator
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(1)
• space requirements: 2n
• first appeared: Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time
• implementions: C++

DABA Lite

• full name: De-Amortized Banker's Aggregator Lite
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(1)
• space requirements: n + 2
• first appeared: In-Order Sliding-Window Aggregation in Worst-Case Constant Time
• implementions: C++

FiBA

• full name: Finger B-Tree Aggregator
• ordering: out-of-order allowed, assumes data is timestamped
• operator requirements: associativity
• time complexity: amortized O(log d) where d is distance newly arrived data is from being in-order, worst-case O(log n); for in-order data (d = 0), amortized O(1) and worst-case O(log n)
• space requirements: O(n)
• first appeared: Optimal and General Out-of-Order Sliding-Window Aggregation
• implementions: C++

FlatFIT

• full name: Flat and Fast Index Traverser
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(n), amortized O(1)
• space requirements: 2n
• first appeared: FlatFIT: Accelerated Incremental Sliding-Window Aggregation For Real-Time Analytics
• implementions: C++ (static windows), C++ (dynamic windows), Rust (dynamic windows)

IOA

• full name: Imperative Okasaki Aggregator
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(1)
• space requirements: O(n)
• first appeared: Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time
• implementions: C++

Two-Stacks

• full name: Two-Stacks
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(n), amortized O(1)
• space requirements: 2n
• first appeared: adamax on Stack Overflow
• implementions: C++, Rust

Two-Stacks Lite

• full name: Two-Stacks Like
• ordering: in-order required
• operator requirements: associativity
• time complexity: worst-case O(n), amortized O(1)
• space requirements: n + 1
• first appeared: In-Order Sliding-Window Aggregation in Worst-Case Constant Time
• implementions: C++, Rust

Reactive

• full name: Reactive Aggregator
• ordering: out-of-order allowed
• operator requirements: associativity
• time complexity: worst-case O(log n)
• space requirements: O(n)
• first appeared: General Incremental Sliding-Window Aggregation
• implementions: C++, Rust

Recalc

• full name: Re-Calculate From Scratch
• ordering: out-of-order allowed
• operator requirements: none
• time complexity: O(n)
• space requirements: n
• first appeared: no known source
• implementations: C++, Rust

SOE

• full name: Subtract on Evict
• ordering: out-of-order allowed
• operator requirements: associativity, invertability
• time complexity: worst-case O(1)
• space requirements: n
• first appeared: no known source
• implementations: C++ (strictly in-order), Rust (strictly in-order)

Amortized MTA (AMTA)

• full name: Amortized Monoid Tree Aggregator
• ordering: in-order required
• operator requirements: associativity
• time complexity:
  • worst-case O(log n), amortized O(1) for insert and evict;
  • worst-case O(1) for query; and
  • worst-case O(log n) for bulkEvict
• space requirements: O(n)
• first appeared: Constant-Time Sliding Window Framework with Reduced Memory Footprint and Efficient Bulk Evictions
• implementions: C++