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