# Do online quantile estimation algorithms that support deletions exist?

There are several online quantile estimation algorithms, but I haven't seen any that supports deletions (i.e. unobserve elements observed in the past). Are there any such known algorithms?

To motivate my question: I'd like to maintain some quantile estimation data structure from the start of time (t0) and take a snapshot of it at t1 and t2. Given the two snapshots, I want to estimate the quantiles for the values observed in [t1,t2] by subtracting the snapshot taking at t1, from the snapshot taken at t2 (i.e. delete all observations in the interval [t0,t1]).

• When it's t1, will you know that? $\:$ If yes, you could just start another online quantile estimation algorithm at that time. $\:$ (Although there could conceivably be a more efficient method.) $\;\;\;\;$ – user12859 May 28 '14 at 20:59
• We don't know t1 and t2 a priori. – tibbe May 29 '14 at 18:42