Exponentially Weighted Simultaneous Estimation of Several Quantiles

Authors: Valeriy Naumov, Olli Martikainen

Abstract:

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.

Keywords: Quantile estimation, data stream, heavy-taileddistribution, tail index.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077112

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.