The P2 Algorithm for Dynamic Calculation of Quantiiles and Histograms Without Storing Observations
Опубликовано на портале: 05-01-2003
Communications of the ACM (CACM). 1985. Vol. 28. No. 10. P. 1076-1085.
"Leonard Francis Zettel, Jr."
A heuristic algorithm is proposed for dynamic calculation of the median and other quantiles. . . . [T]he algorithm has a very small and fixed storage requirement regardless of the number of observations. . . . The algorithm is further extended to histogram plotting. . . . From the Authors' Abstract The algorithm looks interesting and is presented in sufficient detail so that one could implement it. It requires the storage of ten numbers for the calculation of a quantile; thus, it would probably save storage on large samples of observations, since conventional algorithms require the equivalent to access the data sorted from lowest to highest. The analysis that accompanies the algorithm is best described as a lick, a promise, and a bit of arm waving. There is no formal analysis of execution behavior. Nothing is proven about the statistical behavior of the estimators that the algorithm produces. Results of Monte Carlo runs of 50 samples are given for various cases. Similar work presented in the Journal of the American Statistical Association would typically have sample sizes of 10,000. Online Computing Reviews Service
Ссылка на статью находится здесь и на сайте автора