GitHub - IBM/sliding-window-aggregators: Reference implementations of sliding wi...
source link: https://github.com/IBM/sliding-window-aggregators
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
- 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++
- 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)
- 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
- 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
andevict
; - worst-case O(1) for
query
; and - worst-case O(log n) for
bulkEvict
- worst-case O(log n), amortized O(1) for
- space requirements: O(n)
- first appeared: Constant-Time Sliding Window Framework with Reduced Memory Footprint and Efficient Bulk Evictions
- implementions: C++
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK