A billion response times arrive.
You do not need every value on screen.
You need the median.
The 90th percentile.
The 99th.
Perhaps the 99.9th, where the users having the worst experience live.
Quantile sketches exist because sorting and retaining the full stream is often far more expensive than the question requires.
Quick Read
A quantile sketch is a compact summary that supports approximate rank and percentile queries over large datasets or streams. Instead of storing every observation, it retains a carefully selected compressed representation of the distribution.
Modern sketch families differ in what they optimise. KLL-style sketches provide mathematically provable rank-error guarantees. t-digest is an empirical sketch designed for strong practical accuracy, especially near distribution tails. Other sketches optimise relative rank or different error regimes.
One-sentence answer: quantile sketches are lossy because they discard exact observations while preserving enough ordering information to estimate where values sit in a distribution.
A Quantile Is About Position, Not Frequency of One Item
Count-Min Sketch asks how often a particular item appears.
HyperLogLog asks how many distinct items appeared.
A quantile sketch asks something different:
What value lies around a chosen position in the ordered distribution?
The median is the 50th percentile. The 95th percentile is the point below which roughly 95% of observations fall.
That requires preserving order structure without necessarily preserving identity.
Why Exact Quantiles Are Expensive at Scale
If all observations fit comfortably in memory, exact quantiles are straightforward: retain the values, sort them, index the desired rank.
Streaming systems make that harder.
The stream may be larger than memory. It may never end. It may arrive across thousands of machines. The receiver may need updated percentiles continuously.
A sketch turns the distribution into a bounded state.
The Sketch Preserves Order Statistically
A good quantile sketch does not merely average values.
Averages cannot tell you the 99th percentile.
Instead, the sketch retains representative values or weighted summaries across the ordered range so rank questions can later be estimated.
The original stream becomes a much smaller model of its ordering geometry.
Rank Error and Value Error Are Different
This distinction is crucial.
Suppose the true 99th-percentile value is 500 ms.
A sketch may guarantee that the returned value comes from a rank close to the 99th percentile. That is a rank-error guarantee.
But if the distribution is extremely steep near that percentile, a small rank error can translate into a large value error.
Error must be interpreted in the coordinate system the algorithm actually guarantees.
Tails Matter More Than Their Population Size Suggests
The slowest 1% of requests may define user frustration.
The highest 0.1% of pollutant readings may define a safety episode.
The lowest 5% of examination responses may reveal a misconception hidden by the median.
A summary that represents the centre beautifully but blurs the tails may be excellent for one receiver and dangerous for another.
KLL and t-Digest Preserve Different Error Geometry
KLL-style sketches are attractive because their guarantees are mathematical and expressed in rank space.
t-digest is attractive because it often produces particularly strong practical accuracy near extreme quantiles and is widely used in streaming and distributed systems.
These methods should not be collapsed into one vague “percentile algorithm”.
The correct choice depends on which error profile the receiver can tolerate.
Mergeability Changes Distributed Analytics
If every machine must send every raw observation to a central server, the network becomes part of the bottleneck.
Mergeable sketches let each node produce a compact summary that can later be combined.
This preserves a useful algebra over compressed state.
The system loses individual observations but keeps the ability to approximate global quantiles.
Dashboards Depend on This More Than Readers Realise
Large monitoring systems often display p50, p90, p95, p99 and related latency metrics.
At massive scale, those values may come from sketches rather than exact sorted arrays.
The chart can look perfectly precise even though the underlying estimator has a documented error regime.
Good interfaces preserve that epistemic contract when decisions sit near thresholds.
Quantiles Are More Robust Than Means in Some Distributions
A few extreme values can pull an average dramatically.
The median is much less sensitive to a handful of outliers.
This makes quantiles powerful descriptions of skewed distributions.
But robustness is not completeness. A median can remain unchanged while the upper tail becomes catastrophically worse.
Education: Percentiles Are Compressed Cohort Geometry
A percentile tells a student where a score lies relative to a reference group.
It does not reveal the complete distribution, the raw marks, or the knowledge structure behind the scores.
Quantile sketches make that compression computationally efficient at scale, but the educational warning is the same: rank position is not a diagnosis of learning.
When Quantile Sketches Are Exactly the Right Loss
Use them when the stream is huge, percentile queries matter, exact retention is expensive, the required error metric is understood, and detailed source records remain available where audit or reconstruction matters.
They are especially powerful when the receiver needs distribution shape rather than individual history.
When Quantile Sketches Become Dangerous
- Approximate percentiles are treated as exact legal or billing values.
- Rank error is mistaken for value error.
- A centre-accurate sketch is used for a tail-critical decision.
- Sketch parameters differ across nodes that are later merged.
- The display reports more digits than the estimator supports.
- The receiver later needs individual observations that the sketch never retained.
A Practical Quantile-Sketch Audit
- Question: which percentiles matter?
- Error coordinate: rank error, relative rank error, value error or empirical accuracy?
- Tails: are extreme quantiles operationally important?
- Memory: what state budget is available?
- Merge: must distributed summaries combine?
- Display: is output precision aligned with estimator precision?
- Source: is exact evidence retained where necessary?
Sources and Further Reading
- Apache DataSketches: Quantiles Overview, distinguishing KLL, classic, REQ and t-digest error regimes.
- The t-digest: Efficient estimates of distributions.
Continue Through eduKateSG
Continue with How Lossy Works | Probabilistic Sketches, then the companion KLL and t-digest articles.
Final Thought: A Distribution Can Survive After Its Events Disappear
Quantile sketches show one of the deepest forms of useful loss.
The system forgets the individual observations and keeps enough of their ordering structure to answer the questions that still matter.