Skip to content

Reference implementations of sliding window aggregation algorithms

License

Notifications You must be signed in to change notification settings

hirzel/sliding-window-aggregators

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

DABA Lite

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

IOA

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

Reactive

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)

About

Reference implementations of sliding window aggregation algorithms

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 87.4%
  • Rust 7.5%
  • Python 4.6%
  • Other 0.5%