Streaming quantiles

The P² single-quantile estimator — five markers, constant space, an O(1) update per observation, exact below five samples, and gated against a full-sort oracle and the published paper example.

crates/vike-orderflow/src/p2.rs is the one module in the crate that folds nothing from the tape. Its header states what it is: "P² (Jain & Chlamtac 1985) — streaming single-quantile estimator in O(1) space and O(1) per-observation update; the textbook five-marker algorithm with the parabolic (piecewise-parabolic, "P²") marker-height adjustment and the linear fallback when the parabola would break marker monotonicity." It is a "generic utility for future adaptive thresholds (e.g. a VPIN alarm level tracking its own p95)", and the crate "keeps it pure and venue-free like everything else here".

Why a streaming estimator

An exact quantile needs the whole sample sorted. A threshold that tracks its own history — the 95th percentile of every VPIN reading so far — would otherwise hold a growing buffer. P² keeps five numbers and updates them once per observation.

The mechanism

From the header: "five markers track (min, ~p/2, ~p, ~(1+p)/2, max) of the stream. Each observation bumps the positions of the markers above its cell, drifts the DESIRED positions by fixed increments, and nudges any interior marker whose actual position strayed ≥ 1 from desired — parabolic height interpolation when the move preserves q[i−1] < q' < q[i+1], linear otherwise. The p-quantile estimate is the middle marker's height."

The struct's fields say the same in data: q, the five marker heights (q0 the running min, q4 the running max once initialized); n, the actual marker positions — "1-based counts; integer-valued, kept as f64 — every mutation is ±1.0, exact"; np, the desired positions; dnp, the per-observation increments; and init, "the first ≤ 5 observations (init buffer, then frozen)". On the fifth observation the buffer is sorted into the markers, and the desired positions and their increments are seeded as [1, 1+2p, 1+4p, 3+2p, 5] and [0, p/2, p, (1+p)/2, 1].

The surface

pub struct P2Quantile { /* five markers + an init buffer */ }

impl P2Quantile {
    pub fn new(p: f64) -> Self;        // asserts 0 < p < 1, finite
    pub fn push(&mut self, x: f64);    // NaN is ignored
    pub fn value(&self) -> Option<f64>;
    pub fn count(&self) -> u64;
}

push folds one observation; "NaN is ignored (a poisoned marker never recovers)". value is "the middle marker once ≥ 5 observations exist; the exact interpolated sample quantile of the buffer below that; None when empty". The header's reason for the small-sample rule is that "the algorithm is undefined below 5".

The exact form used under five samples is interp_sorted, the linear-interpolated quantile of an ascending-sorted slice: "rank r = p·(m−1), value = v[⌊r⌋] + frac·(v[⌊r⌋+1] − v[⌊r⌋])". The tests walk it for the median: after 4 and 2 the value is 3; after 4, 2 and 6 it is 4; after 0, 2, 4 and 6 it is 3.

An estimate, not a rank

From the fifth observation on the value is the middle marker's height. It starts as the middle of the sorted first five — still an element of the sample — and each adjustment after that moves it by interpolation, so once the marker has moved it is generally no longer a value the stream contained. The parabolic step moves a marker to where the local density suggests the quantile sits; the linear fallback is taken only when that move would cross a neighbouring marker.

How it is gated

The crate header says p2 "is gated against an exact full-sort quantile oracle + the published paper example", and the module's tests spell out both:

The paper's worked example. Table I of Jain & Chlamtac (1985): 20 observations at p = 0.5, whose final middle-marker height the paper gives as 4.44063. The estimator reproduces it within 1e-4, with count() reading 20.
Against the oracle. Over 1000 deterministic uniforms (an LCG in the test — no random dependency) the estimate lands within 0.02 of the exact sorted quantile for p in 0.95; over 2000 skewed samples (the cube of a uniform) within 0.03 for p in 0.9 — "a distribution-shape robustness check, looser gate".
Invariants. Under a mixed stream the markers stay sorted and the estimate stays within the [min, max] of everything seen; a stream with NaNs interleaved counts only the finite observations and still yields a finite value.

Where it stands

The chart's study registry (crates/vike-chart/src/studies.rs) imports Vpin, ImbalanceTracker and OtrTracker from this crate and not P2Quantile; the module header files it under "future adaptive thresholds", and the crate header lists it beside the microstructure studies for that reason. It is the missing piece between a toxicity level and an alarm — the part that decides what "high" means for this instrument, from this instrument's own history.