The P² algorithm for dynamic calculation of quantiles and histograms without storing observations

by Raj Jain, Imrich Chlamtac · 1985
DOI: 10.1145/4372.4378

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.

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.

Reference

Raj Jain, Imrich Chlamtac “The P² algorithm for dynamic calculation of quantiles and histograms without storing observations” (1985) DOI: 10.1145/4372.4378

@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}
}