Quantiles, Ranks & Distribution Summaries

Where Does This Value Rank?

Imagine lining up ten delivery times: 1, 2, 2, 3, 4, 5, 7, 8, 9, 40 minutes. The middle of the queue is near 4–5 minutes, but the last delivery took 40. An average cannot tell a customer how often deliveries run late. A rank counts how many observations lie at or below a value; a quantile names a value at a chosen position in the ordered data. For this list the empirical 90th-percentile nearest-rank value is the ninth observation, 9; the maximum is 40. If observations arrive continually, keeping every value for sorting may be too expensive. How many stored values suffice to answer percentile questions within an acceptable rank error? What changes when some observations represent thousands of requests? The sampling and concentration prerequisites explain why randomness can control error, but a rank bound requires its own explicit statement.

Ranks, Quantiles and Approximate Order

Let $x_1,\ldots,x_N$ be observations from a totally ordered domain, with $N>0$. Define the inclusive rank $r(v)=\#\{i:x_i\leq v\}$. If equal values occur, the lower rank $r_{\lt }(v)=\#\{i:x_i\lt v\}$ and upper rank $r(v)$ bracket the entire tie block. Under the nearest-rank convention, the $q$-quantile for $0\lt q\leq1$ is the value at sorted position $\lceil qN\rceil$. An additive rank-error contract seeks a returned stored value with some valid position within $\varepsilon N$ of $qN$; ties require comparing rank intervals with the target rather than assuming one unique rank. An $\varepsilon$-approximation of the empirical CDF means $\lvert\widehat F(v)-F(v)\rvert\leq\varepsilon$ for every query value $v$, where $F(v)=r(v)/N$. A CDF guarantee for all values implies a rank guarantee when carefully inverting around jumps; a few accurate reported quantiles do not necessarily provide an accurate CDF everywhere. Greenwald–Khanna (GK) maintains deterministic rank intervals in an insertion-only stream and offers $O(\varepsilon^{-1}\log(\varepsilon N))$ space in its standard analysis, with convention-dependent constants. KLL uses randomized weighted compaction and offers high-probability rank error with space depending on $\varepsilon$ and failure probability; state the chosen variant's bound when implementing it. A t-digest often prioritizes tail accuracy empirically, but its common deployments do not furnish a universal worst-case rank guarantee equivalent to GK. A q-digest assumes a bounded ordered integer domain; histograms partition value space and can lose ordering detail within a bin. Weighted quantiles replace each item by a positive weight $w_i$ and normalize rank by $W=\sum_iw_i$; signed weights do not define an ordinary CDF.

flowchart TD
 A["Ordered insertion stream"] --> B["Inclusive rank and tie intervals"]
 B --> C["Nearest-rank quantile"]
 B --> D["Empirical CDF"]
 A --> E["GK rank intervals"]
 A --> F["KLL random compaction"]
 E --> G["Bounded rank error"]
 F --> G
 G --> H["Threshold decision with guard band"]
 classDef navy fill:#17365D,color:#fff
 classDef teal fill:#147D84,color:#fff
 classDef crimson fill:#C6284D,color:#fff
 classDef purple fill:#6C3BAA,color:#fff
 class A,B navy
 class C,D teal
 class E,F purple
 class G,H crimson

Compaction Error and Rank Guarantees

A deterministic summary records a rank interval for each retained value. In GK, a tuple $(v,g,\Delta)$ has lower-rank increment $g$ and uncertainty $\Delta$; the upper rank of a stored value is at most its lower rank plus $\Delta$, and compression preserves a global rank-slack invariant on the order of $2\varepsilon N$. A query selects a value whose feasible rank interval meets the requested position to achieve its specified additive rank tolerance. This guarantee is about positions, not the numeric gap between values: if an extreme outlier sits next to the chosen rank, a one-rank discrepancy can change the reported value enormously. KLL instead groups values at levels. On an even sorted buffer $(a,b,c,d)$, randomly keeping either positions $(a,c)$ or $(b,d)$ with doubled weights preserves total represented weight and yields an unbiased prefix-weight estimate at every fixed query threshold: within each pair, either 0 or 2 represents the pair's true count of 1 for thresholds between the pair's values, with mean 1. Independent level compactions and a carefully allocated capacity schedule bound cumulative rank error with high probability. That argument needs the specified randomness and update/merge model; choosing one parity deterministically on an adversarial order may bias particular ranks. Merging same-parameter KLL summaries can preserve its designated error contract if compaction and seed semantics are respected; a generic deterministic GK merge does not inherit a guarantee merely because each input has one. Repeated observations need tie handling, and weighted streams require a weight-aware implementation rather than blindly expanding huge weights.

flowchart TD
 A["Positive ordered observations"] --> B["Track rank intervals in GK"]
 A --> C["Sort and compact pairs in KLL"]
 B --> D["Maintain global rank slack"]
 C --> E["Random parity; double weights"]
 E --> F["Unbiased prefix estimate"]
 F --> G["Concentration across levels"]
 D --> H["Rank-error query"]
 G --> H
 A --> X["Signed or arbitrary merges"]
 X --> Y["Recheck assumptions"]
 classDef navy fill:#17365D,color:#fff
 classDef teal fill:#147D84,color:#fff
 classDef crimson fill:#C6284D,color:#fff
 classDef purple fill:#6C3BAA,color:#fff
 class A,B,C navy
 class D,E teal
 class F,G,H purple
 class X,Y crimson

Latency Percentiles and Sensor Distributions

A small team can monitor call-center wait times to ask whether 90% of callers wait no longer than a threshold. In a production service, a fleet of 200 instances emits about $10^7$ latency events per minute; fixed one-minute windows, arrival completeness, units, and a defined per-request weight matter as much as the sketch. A global percentile requires combining counts or compatible summaries across instances: averaging per-instance p99 values generally gives the wrong global p99. If an incident sends only slow requests through one tiny instance, equal weighting of instances hides real traffic proportions. For sensor data, a reading repeated because a device retries can shift percentiles without any physical change; deduplicate or clarify that the population is messages rather than sensors. An adversary may also inject extreme samples: rank guarantees remain valid for observed events but cannot certify that events are authentic. A rank-error budget of $0.001N$ at $N=10^7$ spans ten thousand positions; whether that is acceptable for p99.9 depends on the tail density and the SLO decision boundary. Validate numeric-value sensitivity separately.

Design a Percentile Monitoring Contract

Specify the population, event-time window, desired percentiles, tie and weight conventions, allowable rank error, failure probability, and merge policy. Separate a rank guarantee from a numerical latency tolerance or a guarantee that an SLO threshold is exceeded. Select GK when deterministic insertion-only rank intervals and its update model fit; use a correctly configured mergeable randomized sketch when distributed merging is essential; use a histogram when known bin resolution is enough. Check exact sorted samples near the decision boundary and include repeated values, missing events, outliers and shard imbalance. The exercises below lead from hand ranks to a reviewable percentile monitoring contract. The probability-concentration prerequisite supports interpreting randomized failure, while sampling principles help check whether the collected stream represents the intended population.