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

Raj Jain; Imrich Chlamtac

doi:10.1145/4372.4378

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

Raj Jain
, Imrich Chlamtac

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

135 Scopus citations

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.

Original language	English
Pages (from-to)	1076-1085
Number of pages	10
Journal	Communications of the ACM
Volume	28
Issue number	10
DOIs	https://doi.org/10.1145/4372.4378
State	Published - Oct 1 1985

Access to Document

10.1145/4372.4378

Cite this

@article{4b6527593f12433e819bea77b5c835a1,

title = "The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations",

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.",

author = "Raj Jain and Imrich Chlamtac",

year = "1985",

month = oct,

day = "1",

doi = "10.1145/4372.4378",

language = "English",

volume = "28",

pages = "1076--1085",

journal = "Communications of the ACM",

issn = "0001-0782",

number = "10",

}

TY - JOUR

T1 - The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations

AU - Jain, Raj

AU - Chlamtac, Imrich

PY - 1985/10/1

Y1 - 1985/10/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0022144687

U2 - 10.1145/4372.4378

DO - 10.1145/4372.4378

M3 - Article

AN - SCOPUS:0022144687

SN - 0001-0782

VL - 28

SP - 1076

EP - 1085

JO - Communications of the ACM

JF - Communications of the ACM

IS - 10

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this