Communications of the ACM (CACM)
The P2 Algorithm for Dynamic Calculation of Quantiiles and Histograms Without Storing Observations [статья]
Опубликовано на портале: 05-01-2003Raj Jain, Imrich Chlamtac 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.