The Quantile Keeps Five Markers
A running average has a friendly recurrence. A running quantile does not.
If the next observation is huge, the mean knows exactly how much to move. The median has a different problem: it is not a sum, it is a rank. To know whether the middle moved, the obvious algorithm stores the observations, sorts them, and asks for the item at the target rank.
The P2 algorithm is a small, useful gamble against that storage bill. Raj Jain
and Imrich Chlamtac introduced it in 1985 for dynamic quantile and histogram
calculation without storing the observations.1 For one target quantile
p, it keeps five markers:
q1 = current minimum
q2 = current estimate of the p/2 quantile
q3 = current estimate of the p quantile
q4 = current estimate of the (1+p)/2 quantile
q5 = current maximum
The third marker is the answer. The other four markers are there so the answer has a local shape to lean on.
What The Markers Remember
Each marker has two coordinates:
q_i height: the value estimate
n_i position: how many observations should sit at or below it
n_i* desired position: where that marker would be on the ideal CDF
After the first five observations are sorted, the marker heights are just those five values. From then on, each new observation finds the cell it belongs to, increments the actual positions to its right, and advances the desired positions by fixed amounts:
dn* = [0, p/2, p, (1+p)/2, 1]
For a prefix of length n, the desired positions are:
n1* = 1
n2* = 1 + (n-1)p/2
n3* = 1 + (n-1)p
n4* = 1 + (n-1)(1+p)/2
n5* = n
When a middle marker is at least one position away from where it wants to be, and moving it would not collide with a neighbor, P2 moves it by one position. The height update first tries the parabolic interpolation through the three adjacent markers:
d in {-1, +1}
q_i' = q_i + d/(n_{i+1} - n_{i-1}) * (
(n_i - n_{i-1} + d) * (q_{i+1} - q_i) / (n_{i+1} - n_i)
+ (n_{i+1} - n_i - d) * (q_i - q_{i-1}) / (n_i - n_{i-1})
)
If that prediction would break the sorted order of marker heights, the algorithm falls back to a linear step toward the neighbor in the direction of travel:
q_i' = q_i + d * (q_{i+d} - q_i) / (n_{i+d} - n_i)
This is why the estimator feels unlike a histogram. It is not counting in fixed buckets. It is dragging a tiny sketch of the empirical CDF through the stream.
Lab: The Markers Chase The Rank
The lab compares the P2 estimate with an exact prefix quantile computed from the stored sorted observations. The exact line is allowed to cheat. The P2 line only sees one observation at a time and keeps five marker heights.
The exact reference stores the whole prefix and uses the paper-style rounded order statistic. P2 keeps only five marker heights for this one target quantile.
On the default run, the stored exact p95 and the P2 estimate nearly agree, but that is an empirical result of this stream, not a theorem. Change the stream to the regime shift and watch the interpretation change: P2 is estimating the quantile of the whole prefix, not the latest regime. The “lag” is not a bug in that setting. It is the question being asked.
What The Audit Checks
The exported Node audit runs three stream families at p50, p90, and p95. For each run it reports seven named checks:
the generated sample count matches the requested count
marker heights stay in nondecreasing order
actual marker positions stay strictly increasing
desired marker positions stay monotone and finite
the estimate remains inside the observed value range
the exact and estimated history are finite
the final estimate has rank error no larger than 0.12
It also reports two default-run sanity checks: the estimator has exactly five markers, and this default stream uses more parabolic moves than linear fallback moves.
Ignoring the returned case rows, the current top-level summary is:
{
"defaultAbsError": 0.981,
"defaultRankError": 0.0036,
"ok": true,
"passed": 9,
"passedChecks": 65,
"scenarios": 3,
"total": 9,
"totalChecks": 65
}
The compact reproduction check is:
const lab = require("./assets/js/p2-quantile-lab.js");
const EXPECTED_CASE_SHAPE = [
"1:latency:p50:seed=23:samples=2600:exact=43.3848:estimate=43.325:abs=0.0598:rank=0.0015:moves=1514/0:checks=7/7",
"2:latency:p90:seed=23:samples=2600:exact=64.3657:estimate=64.1738:abs=0.1919:rank=0.0012:moves=724/3:checks=7/7",
"3:latency:p95:seed=23:samples=2600:exact=73.08:estimate=72.6664:abs=0.4136:rank=0.0019:moves=614/2:checks=7/7",
"4:drift:p50:seed=23:samples=2600:exact=47.0461:estimate=47.3382:abs=0.2921:rank=0.01:moves=2944/0:checks=7/7",
"5:drift:p90:seed=23:samples=2600:exact=65.1428:estimate=67.4667:abs=2.3239:rank=0.0331:moves=2566/0:checks=7/7",
"6:drift:p95:seed=23:samples=2600:exact=69.02:estimate=71.6067:abs=2.5867:rank=0.0192:moves=2133/2:checks=7/7",
"7:shift:p50:seed=23:samples=2600:exact=36.0931:estimate=46.2982:abs=10.2051:rank=0.0804:moves=2394/0:checks=7/7",
"8:shift:p90:seed=23:samples=2600:exact=84.0857:estimate=85.2701:abs=1.1844:rank=0.0146:moves=1545/1:checks=7/7",
"9:shift:p95:seed=23:samples=2600:exact=87.6772:estimate=88.7412:abs=1.0641:rank=0.0104:moves=1279/1:checks=7/7"
];
const EXPECTED_CHECK_NAMES = [
"sample-count",
"marker-heights-ordered",
"marker-positions-increasing",
"desired-positions-monotone",
"estimate-inside-range",
"finite-history",
"rank-error-threshold"
];
const EXPECTED_DEFAULT_SHAPE =
"10:default stream sanity checks:checks=2/2";
const EXPECTED_DEFAULT_CHECK_SHAPE = [
"10:default:default-run-has-five-markers:true",
"10:default:default-run-prefers-parabolic-moves:true"
];
const EXPECTED_CASE_IDS = EXPECTED_CASE_SHAPE.map((shape) =>
shape.split(":").slice(0, 3).join(":")
);
const EXPECTED_CHECK_SHAPE = EXPECTED_CASE_IDS.flatMap((caseId) =>
EXPECTED_CHECK_NAMES.map((name) => `${caseId}:${name}:true`)
).concat(EXPECTED_DEFAULT_CHECK_SHAPE);
const EXPECTED_SCENARIOS = new Set(
EXPECTED_CASE_IDS.map((caseId) => caseId.split(":")[1])
).size;
const EXPECTED_PERCENTILES = new Set(
EXPECTED_CASE_IDS.map((caseId) => caseId.split(":")[2])
).size;
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_DETAIL_ROWS = EXPECTED_CASES + 1;
const EXPECTED_CHECKS = EXPECTED_CHECK_SHAPE.length;
function sameList(actual, expected) {
return actual.length === expected.length &&
actual.every((value, index) => value === expected[index]);
}
function caseShape(row) {
return `${row.caseId}:${row.scenario}:p${row.percentile}:` +
`seed=${row.seed}:samples=${row.samples}:` +
`exact=${row.exact}:estimate=${row.estimate}:abs=${row.absError}:` +
`rank=${row.rankError}:moves=${row.parabolicMoves}/${row.linearMoves}:` +
`checks=${row.passedChecks}/${row.totalChecks}`;
}
function defaultShape(row) {
return `${row.caseId}:${row.label}:checks=${row.passedChecks}/${row.totalChecks}`;
}
function checkShape(row) {
const id = row.scenario
? `${row.caseId}:${row.scenario}:p${row.percentile}`
: `${row.caseId}:default`;
return row.checks.map((check) => `${id}:${check.name}:${check.ok}`);
}
const audit = lab.auditP2QuantileLab();
const shape = {
cases: audit.cases.map(caseShape),
checks: audit.details.flatMap(checkShape),
default: defaultShape(audit.defaultChecks),
scenarios: audit.scenarios,
scenarioRows: new Set(audit.cases.map((row) => row.scenario)).size,
percentiles: new Set(audit.cases.map((row) => row.percentile)).size,
detailRows: audit.details.length
};
const shapeErrors = [];
if (!sameList(shape.cases, EXPECTED_CASE_SHAPE)) {
shapeErrors.push({ name: "cases", actual: shape.cases, expected: EXPECTED_CASE_SHAPE });
}
if (!sameList(shape.checks, EXPECTED_CHECK_SHAPE)) {
shapeErrors.push({
name: "checks",
actual: shape.checks,
expected: EXPECTED_CHECK_SHAPE
});
}
if (shape.default !== EXPECTED_DEFAULT_SHAPE) {
shapeErrors.push({
name: "default",
actual: shape.default,
expected: EXPECTED_DEFAULT_SHAPE
});
}
const summary =
`${audit.passed}/${audit.total} cases and ` +
`${audit.passedChecks}/${audit.totalChecks} checks passed`;
const failedCases = audit.details.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (shapeErrors.length ||
failedCases.length ||
!audit.ok ||
shape.scenarios !== EXPECTED_SCENARIOS ||
shape.scenarioRows !== EXPECTED_SCENARIOS ||
shape.percentiles !== EXPECTED_PERCENTILES ||
audit.cases.length !== EXPECTED_CASES ||
shape.detailRows !== EXPECTED_DETAIL_ROWS ||
audit.total !== EXPECTED_CASES ||
audit.totalChecks !== EXPECTED_CHECKS ||
audit.passed !== audit.total ||
audit.passedChecks !== audit.totalChecks) {
throw new Error(JSON.stringify({
summary,
shapeErrors,
errors: audit.errors.slice(0, 10),
failedCases,
totals: {
cases: audit.cases.length,
detailRows: shape.detailRows,
passed: audit.passed,
passedChecks: audit.passedChecks,
total: audit.total,
totalChecks: audit.totalChecks
}
}, null, 2));
}
console.table(audit.cases.map((row) => ({
stream: row.scenario,
percentile: "p" + row.percentile,
absError: row.absError,
rankError: row.rankError,
parabolicMoves: row.parabolicMoves,
linearMoves: row.linearMoves,
checks: `${row.passedChecks}/${row.totalChecks}`
})));
console.log(summary);
That last rank-error threshold is deliberately loose because P2 is a heuristic. The useful fact to test is not “this always nails p95.” It is:
with five markers, on these deterministic streams,
the estimator remains ordered, finite, inspectable, and close enough to compare
What This Is Not
P2 is not a mergeable quantile sketch. If two machines each keep five P2 markers, there is no general operation that combines those ten markers into the same result as processing the raw observations in one order. That is a major difference from the sketching problem faced by distributed observability systems.
P2 also does not give the deterministic rank-error contract associated with formal streaming summaries. It is appealing because the memory is tiny and constant. That appeal is real. So is the cost: accuracy is something you measure for the streams you care about.
The five markers are a good mental model for a broader lesson. Approximate statistics are not just smaller exact statistics. They carry a contract. Here the contract is:
one target quantile
one pass
fixed memory
not mergeable
empirical accuracy
That is a perfectly respectable contract, as long as it is the one you meant to sign.
-
Raj Jain and Imrich Chlamtac, “The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations”, Communications of the ACM 28(10), 1985, pp. 1076-1085. Metadata and abstract are available through WashU Research Profiles. A public PDF is hosted by Raj Jain’s Washington University page: psqr.pdf. ↩