R. Jain and I. Chlamtac, "The P-Square Algorithm for Dynamic Calculation of Percentiles and Histograms without Storing Observations," Communications of the ACM, October 1985.


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.

Complete Paper in Adobe Acrobat (814,451 Bytes) |

Back to the List of Papers
Back to Raj Jain's home page