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

1985/10/01 by Raj Jain, Imrich Chlamtac · 8 citations
Computer Science · #Numerical Methods and Algorithms

paper · pdf · doi:10.1145/4372.4378

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\n non-stationary data streams
• Stream quantiles via maximal entropy histograms
• Trace Sampling 2.0: Code Knowledge Enhanced Span-level Sampling for Distributed Tracing
• 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\n 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