5
$\begingroup$

I am looking for an algorithms to maintain several statistics over a sliding window. The setup is as follows: There is a datastream consisting of (real value,timestamp) tuples. The values for the last x seconds are stored. In each iteration at least one new tuple arrives and between zero and more values are retired. Now I want to maintain mean and variance without recomputing everything from scratch. There are methods if values are never retired, e.g. Welford's method. But what if values are retired?

The second problem I am facing is, how to compute covariance between two sliding windows in a similar fashion?

Are you aware of a solution or references?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! 1. Please define what you mean by "retired". What effect should that have on the output? 2. Do you want the mean of all the values that have arrived up until now? If so, why isn't this problem trivial? Just compute the sum of all the values and the count of the number of values. You can also compute the variance by computing the sum of the squares of the values. So why aren't those standard methods suitable? 3. Please stick to one question per question. If you have a second question (e.g., about covariance), post it separately as a separate question. Thank you! $\endgroup$ – D.W. Apr 5 '15 at 0:03
  • 1
    $\begingroup$ 1. Retired means, values leave the sliding window. A sliding window is defined e.g. as 'the last hour till now'. So values older than one hour are retired/dropped/deleted. I always want to compute the statistics for the values in the sliding window as defined above. $\endgroup$ – Johannes Apr 5 '15 at 12:39
  • 1
    $\begingroup$ 2. First: I want to have statistics of all values in the sliding window. So the influence of retired values has to be compensated. Second: The standard methods are in some cases not suitable since catastrophic cancellation can lead to wrong results (e.g. negative variance), see also the link in my original question. 3. I was hoping there was a paper/reference or something that answers these question, I would have imagined this was out there, but could not find it. $\endgroup$ – Johannes Apr 5 '15 at 12:46
  • $\begingroup$ How much memory do you have? Do you have enough memory to store all of the values in the sliding window? Or is the amount of memory you have only a small fraction of what would be needed to store all of the values in the sliding window? That could impact the best solution. If the latter, when a value expires (leaves the window), do you recieve an event telling you what the value was, or not? This impacts the model of computation. $\endgroup$ – D.W. Jul 8 '15 at 22:01
2
$\begingroup$

To compute the mean of all the values in your window, separately compute (a) the sum of all the values in the window, and (b) a count of the number of values in the window.

To keep track of the sum of all the values in the sliding window, each time you receive a new value, add it to the sum. Each time a value leaves the window, subtract it from the sum. Now you'll always have a sum of the values in the window.

To keep track of the number of values in the window, each time you receive a new value, increment the counter. Each time a value leaves the window, decrement the counter.

Finally, the mean is the sum divided by the count.

To keep track of the variance, you need the count, the sum of the values, and the sum of the squares of the values. You can keep track of the sum of the squares of the values in the window in the same way (when a new value arrives, add its square to the running sum; when a value leaves, subtract its square). These three values are enough to let you compute the variance of the values in the sliding window.

Note that when using the sum of squares method to compute the variance, you will need to compute the three intermediate values to enough digits of precision. If you don't have enough digits of precision for those intermediate values, then you get a very inaccurate estimate. This is the robustness problem that is mentioned in the blog post you link to and that is addressed by Welford's method. However, there is another pragmatic way to address it that will work for most practical settings: just compute those three intermediate values to more digits of precision.

For the covariance between $x_1,\dots,x_n$ and $y_1,\dots,y_n$, you need to know the sum of the values $x_i$, $x_i^2$, $y_i^2$, $x_i y_i$, and the count $n$. So, it's basically the same principle as above, but now there are five intermediate values you need to maintain, instead of just three.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Increasing the precision is no alternative for me, though. $\endgroup$ – Johannes Apr 7 '15 at 15:10
  • $\begingroup$ @Johannes, if it's not an option for you, then you have not described all of your requirements in the question. If you haven't defined all of the requirements in your question, then your problem is not well-posed, and you should edit the question. (Incidentally, if you already knew of this approach and knew it wasn't workable, then you should mention it in your question so that I don't waste time typing up something you already know isn't what you want. See also cs.stackexchange.com/help/how-to-ask.) $\endgroup$ – D.W. May 6 '15 at 0:33
2
$\begingroup$

Usually, an exact solution is impossible (unless you keep the entire window in memory), however it is possible to approximate the output as a function of the amount of memory you are allowed to have. A good starting point would be

They show how to maintain the sum of a positive-value data stream (then, computing the average is just dividing in the window's size). The mainly assume a fixed window size (i.e., at each time step a new item arrives and one old item expires), however they also discuss the model you are interested in, where each element has a time-stamp, and several items may expire at the same time. Check if Exponential Histogram (or their extension, smooth histograms) may give you what you need.

Another good source of information for data streams in general would be the survey

$\endgroup$
  • $\begingroup$ Good stuff. Usually, it's impossible, but for the specific case asked about in the question (mean and variance), it is possible in some cases, because of the structure of the mean and variance. In particular, if you can store all of the values in the sliding window (or if each time a value expires, you receive a notification telling you what the value was), it is possible to compute an exact answer. Those papers focus more on other cases where you can't get an exact solution. For instance, consider the mean: ignoring precision, it's enough to simply keep track of a running sum and count. $\endgroup$ – D.W. Jul 8 '15 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.