2
$\begingroup$

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]).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\;\;\;\;$ $\endgroup$ – user12859 May 28 '14 at 20:59
  • $\begingroup$ We don't know t1 and t2 a priori. $\endgroup$ – tibbe May 29 '14 at 18:42

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.