# Computing a rolling quantile

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.

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.
• +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.) – Erik P. Feb 27 '12 at 15:11