AssociativeWindowAggregation.jl
Accumulate binary associative operators over rolling windows.
Features
- Supports any binary operator that is associative (see Assumptions section for an elaboration).
- Supports a potentially variable window size.
- Supports adding values incrementally, e.g. when streaming data.
- Runs in amortized
O(1)
time, and usesO(L)
space, whereL
is the typical window length.
Assumptions and stability
We assume that operators are associative. Strictly speaking this is not true for most operations on floating point numbers, however without this assumption one can do no better than O(L)
time complexity. Practically, for most reasonable applications this assumption is reasonable.
As detailed below, there is no long-term accumulation of errors.
Note that we do not assume:
- The existence of an inverse
- Commutativity
Example
Consider computing a rolling sum over [a, b, c, d, e]
with window size 3
. Ignoring the first two incomplete elements, we will emit exactly:
[
a + b + c,
b + c + d,
c + d + e
]
Note that the most common O(1)
approach to computing rolling sums uses the following approximation:
[
a + b + c,
a + b + c - a + d,
a + b + c - a + d - b + e
]
This can be problematic due to overflow / underflow for most numerical types, and accumulated rounding errors in floating point types (for an extreme example, suppose a
is Inf
). The simple approach also does not generalise to operators like the set union
, since there is no inverse.