A Technique with Low Memory and Computational Requirements for Dynamic Tracking of Quantiles

A technique for dynamic tracking of quantiles of data streams, without storage and sorting of past data samples, is presented. It updates the quantile estimate recursively by applying an increment, selected as a fraction of the range, such that the estimated quantile approaches the sample quantile. The range is dynamically estimated using first-order recursive relations for peak and valley detection. The technique does not require initial estimates and the computation steps involved are the same for all the samples. It has low memory and computational requirements and is suitable for signal processing and other applications involving online tracking of single or multiple quantiles of data streams. It has been tested using synthetic and real data with different distributions.