Online estimation of quartiles without storing observations

I need to compute quartiles (Q1,median and Q3) in real-time on a large set of data without storing the observations. I first tried the P square algorithm (Jain/Chlamtac) but I was no satisfied with it (a bit too much cpu use and not convinced by the precision at least on my dataset).

I use now the FAME algorithm (Feldman/Shavitt) for estimating the median on the fly and try to derivate the algorithm to compute also Q1 and Q3 :

M = Q1 = Q3 = first data value
step =step_Q1 = step_Q3 = a small value
for each new data :
# update median M
if M > data:
M = M - step
elif M < data:
M = M + step
if abs(data-M) < step:
step = step /2

# estimate Q1 using M
if data < M:
if Q1 > data:
Q1 = Q1 - step_Q1
elif Q1 < data:
Q1 = Q1 + step_Q1
if abs(data - Q1) < step_Q1:
step_Q1 = step_Q1/2
# estimate Q3 using M
elif data > M:
if Q3 > data:
Q3 = Q3 - step_Q3
elif Q3 < data:
Q3 = Q3 + step_Q3
if abs(data-Q3) < step_Q3:
step_Q3 = step_Q3 /2

To resume, it simply uses median M obtained on the fly to divide the data set in two and then reuse the same algorithm for both Q1 and Q3.

This appears to work somehow but I am not able to demonstrate (I am not a mathematician) . Is it flawned ? I would appreciate any suggestion or eventual other technique fitting the problem.

Thank you very much for your Help !

==== EDIT =====

For those who are interested by such questions, after a few weeks, I finally ended by simply using Reservoir Sampling with a revervoir of 100 values and it gave very satistfying results (to me).

• Are you looking for a proof that Q1 and Q2 converge to the true quantiles as the number of examples increase in a manner similar to the markov chain analysis in the slides you linked? In terms of implementation, the above algorithm does not seem flawed (I tested approximating quantiles for standard normal in R and the algorithm works fine). – Theja Jun 13 '14 at 15:25
• @Theja thank you, I am not looking for a proof (too much work) but merely advices and comments, The main problem I see is to base the computation on running estimate of the median, as whuber has pointed. – Louis Hugues Jun 13 '14 at 15:33

• Wouldn't directly estimating the quartiles be subject to similar issues? Direct estimation would partition the $n$ data points into a $1:3$ ratio. This partitions the elements into $2:2$ and then takes one of those "2"s and splits it $1:1$. I'm no theoretician, true, but, in general, wouldn't the difference between the two be different by at most one spot to the left or right and would converge as $n$ increases? Yes, a pathological distribution could be created, but that would suffer from direct median estimation as well. Obviously, storing all the values is better, of course. – Avraham Jun 13 '14 at 15:32