Time windowed online variance algorithm

Question

I'm trying to find an efficient, online algorithm for computing the rolling variance in a predefined time window (e.g. the last 5 minutes). It needs to be efficient in the sense that I can't hold on to all the data points within the time window, as they arrive at a frequency of 10M data points per second. Ideally the algorithm should also be numerically stable. I'm aware of the Welford's algorithm for non-windowed rolling variance.

I am aware of other SO answers for fixed-size windows. I believe this is a different question.

Answer 1

I think you will have a problem solving this exactly as stated.

Consider a stream of bits encoded as pairs of floating point samples 1 = {0.0, 0.0} 0 = {-1.0, 1.0}. If I feed the result of encoding an arbitrary bitstream the size of the window to your algorithm and then send in a stream of zeros, the variance your algorithm reports will fluctuate depending on whether the sample pair that just dropped off the far edge of the window was {0.0, 0.0} or {-1.0, 1.0}.

So I can use your algorithm to memorize a bitstream of about half the size of the sliding window. So your algorithm cannot be implemented without using about this much storage.

Perhaps you could use some form of exponential smoothing. Simple exponential smoothing is equivalent to a weighted mean in which the weights decay exponentially, and if you smooth the squared values you will get an exponentially weighted sum of squares. If you also have an exponentially weighted sum of unsquared values, you could combine the two to get an exponentially weighted sum of squared deviations from some central value, for any desired central value. Of course, you would need to improve this idea significantly to get something numerically stable - perhaps this is covered in the detail of one of the weighted variance algorithms at the end of the Wikipedia article you cited.

Answer 2

This is an answer to tibbe's comment about how to combine means and variances.

In words, the combined mean is the mean of the means, and the combined variance is the sum of the mean of the variances and the variance of the means.

More formally: suppose we have the count n, the mean m and the variance mean for k subsets of data; assuming that the subsets are disjoint, the count N, mean M and variance V of the union of the k subsets can be computed by:

N = Sum{ n[i] }
M = Sum{ w[i]*m[i] }
V = Sum{ w[i]*v[i] } + Sum{ w[i]*(m[i]-M)*(m[i]-M)}
where
w[i] = n[i]/N