Skip to content

Reference implementations of sliding window aggregation algorithms

License

Notifications You must be signed in to change notification settings

IBM/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

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)

Amortized MTA (AMTA)

About

Reference implementations of sliding window aggregation algorithms

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published