1
$\begingroup$

I'm searching for a computationally efficient algorithm to calculate the sliding mean deviation from sample $x_a$ to sample $x_b$ belonging to a large set $x_0, x_1 ... x_n$ with the condition that $a$ and $b$ are incremented by 1 at every iteration and the window size $a-b$ is constant:

$$\frac{1}{a-b+1} \sum_{i = a}^{b}{|x_i - \bar x_{ab}|} $$

Reiterating the above formula across every window $a,b$ (with $a-b$ constant) in my data set is slow due to the amount of samples and the large window size. I suspect a better method could be used which takes advantage of the already-computed values from the previous window.

Improve this question
$\endgroup$
  • 4
    $\begingroup$ I don't think you'll easily get an appreciable speed up - as the mean changes you'd have to keep track of which points the updated mean crosses over (the ones it stays the same side of would be simpler to deal with), It's conceivable that by maintaining some kind of tree / similar appropriate data structure, you might be able to reduce the computation in the update (allowing quicker updating of points near the mean) but you won't have a neat fast update like you do for the variance, say, because you don't have the neat decompositions like variance has. For large windows there may be some gains $\endgroup$ – Glen_b Apr 9 '17 at 3:05
  • $\begingroup$ @Glen_b that's right. By maintaining two heaps--one for the values above the mean and another for the values below the mean--I believe you can achieve $O(b-a)$ performance for each update on average. I recently implemented that in R (to compute the running absolute deviation around medians) and found it to be too slow to be practicable. If there is any performance to be gained, it will be for an online algorithm (where $n$ constantly grows) and $b-a$ is huge. $\endgroup$ – whuber♦ Apr 9 '17 at 16:22
  • $\begingroup$ @whuber Interesting; it's nice to hear that it worked out much the way I anticipated it would. Funnily enough, I originally wrote "tree, heap or similar data structure" (since a heap seemed a likely candidate for this problem) but ran out of characters and decided to push "heap" into "similar data structure". $\endgroup$ – Glen_b Apr 9 '17 at 22:03

Your Answer

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

Browse other questions tagged or ask your own question.