Algorithm for dynamic control of quantiles (s)

Question

I want to evaluate the quantile of some data. The data is so huge that it will not fit into memory. And new data keeps coming. Does anyone know an algorithm for monitoring the quantiles of data observed so far with very limited memory and computation? I found the P2 algorithm useful. But this does not work very well for my data, which is extremely heavily distributed.

Answer 1

consider dividing the value space into cells in each bin containing a count of values ​​in a range.

You can try to make the bins smaller around the point where you expect the quantile to look.

If you make the number of bins large enough, this should work well.