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

1985/10/01 by Raj Jain, Imrich Chlamtac · 177 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Computer science #Heuristic #Histogram #Ideal (ethics) #Image (mathematics) #Mathematics #Numerical Methods and Algorithms #Quantile #Statistics

paper · pdf · doi:10.1145/4372.4378

published in Communications of the ACM 28(10), 1076-1085 (Association for Computing Machinery)

openalex publication_date 1985/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

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.

Cited by

• Capturing Polysemanticity with PRISM: A Multi-Concept Feature Description Framework
• Two maximum entropy based algorithms for running quantile estimation in non-stationary data streams
• Stream quantiles via maximal entropy histograms
• Trace Sampling 2.0: Code Knowledge Enhanced Span-level Sampling for Distributed Tracing
• Minos: Exploiting Cloud Performance Variation with Function-as-a-Service Instance Selection
• Interpolation methods to compute statistics of a stochastic partial differential equation
• Approximating quantiles in very large datasets
• A Survey of Approximate Quantile Computation on Large-Scale Data
• QUEST: Eliminating Online Supervised Learning for Efficient Classification Algorithms. [europepmc]
• Measuring the effect of negative interest rate on New Zealand banks. [europepmc]
• Estimating cutoff values for diagnostic tests to achieve target specificity using extreme value theory. [europepmc]
• Daily Automated Prediction of Delirium Risk in Hospitalized Patients: Model Development and Validation. [europepmc]

Related

• Two maximum entropy based algorithms for running quantile estimation in non-stationary data streams
• Histogram Specification by Assignment of Optimal Unique Values
• Stream quantiles via maximal entropy histograms
• Approximating quantiles in very large datasets
• The adaptable buffer algorithm for high quantile estimation in non-stationary data streams