Quantile estimation: a minimalist approach

ABSTRACT

Managing telecommunication networks involves collecting and analyzing large amounts of statistical data. The standard approach to estimating quantiles involves capturing all the relevant data (what may require significant storage/processing capacities), and performing an off-line analysis (what may delay management actions). It is often essential to estimate quantiles as the data are collected, and to take management actions promptly. Towards this goal, we present a minimalist approach to sequentially estimating constant/changing over time quantiles. We follow prior work and devise a fixed-point algorithm, which does not estimate the unknown probability density function at the quantile. Instead, our algorithm uses the log-odds transformation of the observed fractions, and the exponentially smoothed estimates of the standard deviation to update the quantile estimate. For large data streams, this algorithm can significantly reduce the amount of collected data and the complexity of data analysis.

References

1. Chen, F., D. Lambert, and J. C. Pinheiro. 2000. Incremental Quantile Estimation for Massive Tracking. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 516--522.]]
2. Chen, J. E., and D. W. Kelton. 2001. Quantile and Histogram Estimation. Proceedings of the Winter Simulation Conference, 451--459. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.]]
3. Chen, J. E. 2002. Two-Phase Quantile Estimation. Proceedings of the 2002 Winter Simulation Conference, 447--455. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.]]
4. Greenwald, M., and S. Khanna, S. 2001. Space-Efficient Online Computation of Quantile Summaries. Proceedings of the ACM SIGMOD Conference, 47--57.]]
5. Lee, J. R., D. McNickle, and K. Pawlikowski. 1998. Sequential Estimation of Quantiles. Technical Report TR-COSC 05/98. Department of Computer Science, University of Canterbury, Christchurch, New Zealand.]]
6. Manku, G. S., S. Rajagopalan, and B. G. Lindsay. 1998. Approximate Medians and other Quantiles in One Pass and with Limited Memory. In Proceedings of the ACM International Conference on Management of Data, 426--435.]]
7. Tierney, L. 1983. A space-efficient recursive procedure for estimating a quantile of an unknown distribution. SIAM Journal on Scientific and Statistical Computing. Vol. 4, Issue 4, 706--711.]]