Эксоцман
на главную поиск contacts

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. 
Тематический раздел:
A heuristic algorithm is proposed for dynamic calculation of the median and other quantiles. The estimates are produced dynamically as the observations are generated. The observations are not stored; therefore, the algorithm has a very small and fixed storage requirement regardless of the number of observations. This makes it ideal for implementing in a quantile chip that can be used in industrial controllers and recorders. The algorithm is further extended to histogram plotting. The accuracy of the algorithm is analyzed.

"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
Ссылка на статью находится здесь и на сайте автора
BiBTeX
RIS
Ключевые слова

См. также: