3
$\begingroup$

An algorithm I'm writing needs to compute rolling quantiles of a time series. Currently I do this in the naive way: for a window of size W and a vector X of size N

for t from W to N:
  q[t,:] = quantiles(X[t-W+1:t])

However, it seems that there should be a faster way, given that I know the previous quantile q[t-1], the new data X[t] and the data X[t-W] that has just dropped out of the window. I'm thinking of something along the lines of the well (?) known incremental mean algorithm:

for t from W to N:
  m[t] = m[t-1] + ( x[t] - x[t-W] ) / W

which avoids recalculating the mean at every stage. Even an approximation would be good. I've seen approximations for computing quantiles on streams, but it is important to me that I have a rolling window, not just an expanding window.

$\endgroup$
4
$\begingroup$

One solution would be to keep your rolling window of data sorted using a self-balancing binary tree or a hash table. On every update, you pay a constant insertion cost, a $O(n)$ deletion cost, and a $O(n)$ traversal cost to update the quintiles.

$\endgroup$
  • $\begingroup$ +1 for the self-balancing tree. How would you use a hash table to maintain a sort order? And I would think that insertion, deletion, and quantile computation are all $O(\log(n))$? (Note also that quantiles are more general than quintiles.) $\endgroup$ – Erik P. Feb 27 '12 at 15:11

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.