Exponentially Weighted Simultaneous Estimation of Several Quantiles

In this paper we propose new method for simultaneous generating multiple quantiles corresponding to given probability levels from data streams and massive data sets. This method provides a basis for development of single-pass low-storage quantile estimation algorithms, which differ in complexity, storage requirement and accuracy. We demonstrate that such algorithms may perform well even for heavy-tailed data.

Authors:

• Valeriy Naumov
• Olli Martikainen

Keywords:

• Quantile estimation
• data stream
• heavy-taileddistribution
• tail index.

References:

[1] C. Hurley and R. Modarres, "Low-storage quantile estimation,"
Computational Statistics, vol. 10, no. 4, 1995, pp. 311-325.
[2] A.M. Law and W.D. Kelton, "Simulation Modeling and Analysis," 3rd
ed. New York:McGraw-Hill, 2000.
[3] L. Tierney, "A space-efficient recursive procedure for estimating a
quantile of an unknown distribution," SIAM J. on Scientific and
Statistical Computing, vol. 4, no. 4, 1983, pp. 706-711.
[4] R. Jain and I. Chlamtac, "The P2 algorithm for dynamic calculation of
quantiles and histograms without storing observations,"
Communications of the ACM, vol. 28, no. 10, 1985, pp. 1076-1085.
[5] K.E.E. Raatikainen, "Simultaneous estimation of several percentiles",
Simulation, vol. 49, no. 4, 1987, pp. 159-164.
[6] K.E.E. Raatikainen, "Sequential procedure for simultaneous estimation
of several percentiles," Trans. of the Society for Computer Simulation,
vol. 7, no. 1, 1990, pp. 21-44.
[7] J.C. Liechty, D.K.J. Lin and J.P. McDermott, "Single-pass low-storage
arbitrary quantile estimation for massive datasets", Statistics and
Computing, vol. 13, 2003, pp. 91-100.
[8] L. Golab and M.T. Özsu, "Issues in data stream management," ACM
SIGMOD Record, vol. 32, No. 2, 2003, pp. 5-14.
[9] F. Chen, D. Lambert and J.C. Pinheiro, "Incremental quantile estimation
for massive tracking," in Proc. 6th ACM SIGKDD Int. Conf. on
Knowledge Discovery and Data Mining, Boston, 2000, pp. 516-522.
[10] B.M. Hill, "A simple general approach to inference about the tail of a
distribution," Annals of Statistics, vol. 3, no. 5 , 1975, pp. 1163-1174.
[11] L. Peng, "Estimating the mean of the heavy tailed distribution,"
Statistics & Probability Letters, vol. 52, no. 3, 2001, pp. 31-40.
[12] B. Abraham and J. Ledolter, "Statistical Methods for Forecasting," New
York:John Wiley & Sons, 1983.
[13] L. Breiman, C.J. Stone and C. Kooperberg, "Robust confidence bounds
for extreme upper quantiles," J. Statist. Comput. Simul., vol. 37, 1990,
pp. 127-149.