The P 2 algorithm for dynamic calculation of quantiles and histograms without storing observations
- 1 October 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 28 (10) , 1076-1085
- https://doi.org/10.1145/4372.4378
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- Implementations for coalesced hashingCommunications of the ACM, 1982
- Optimum Storage Allocation for Initial Loading of a FileIBM Journal of Research and Development, 1972
- Addressing for Random-Access StorageIBM Journal of Research and Development, 1957