Library / The P² Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations

The P² quantile estimator is a fast sequential estimator that uses $O(1)$ memory. Allows implementing lightweight real-time monitoring of various indicators in software systems.

Reference

Raj Jain, Imrich Chlamtac “The P² algorithm for dynamic calculation of quantiles and histograms without storing observations” (1985) // Communications of the ACM. Publisher: Association for Computing Machinery (ACM). Vol. 28. No 10. Pp. 1076–1085. DOI: 10.1145/4372.4378

Abstract

What constitutes a dangerous equation? There are two obvious interpretations: Some equations are dangerous if you know them, and others are dangerous if you do not.

Bib

@Article{jain1985,
  title = {The P² algorithm for dynamic calculation of quantiles and histograms without storing observations},
  abstract = {What constitutes a dangerous equation? There are two obvious interpretations: Some equations are dangerous if you know them, and others are dangerous if you do not.},
  volume = {28},
  issn = {1557-7317},
  url = {http://dx.doi.org/10.1145/4372.4378},
  doi = {10.1145/4372.4378},
  number = {10},
  journal = {Communications of the ACM},
  publisher = {Association for Computing Machinery (ACM)},
  author = {Jain, Raj and Chlamtac, Imrich},
  year = {1985},
  month = {oct},
  pages = {1076–1085}
}

Backlinks (4)

1. Extended P² quantile estimator (2022-01-18) 5 2
2. P² quantile estimator marker adjusting order (2022-01-11) 5 1
3. P² quantile estimator initialization strategy (2022-01-04) 3 2
4. P² quantile estimator: estimating the median without storing values (2020-11-24) 5