How to Learn KLL Quantile Sketches: Compaction Levels, Rank Error, Mergeability and Streaming Percentiles

Wait, What?

You can estimate the median, 95th percentile and much of an enormous data distribution without storing the enormous data distribution.

A KLL quantile sketch is a compact streaming summary designed for approximate rank and quantile queries. Instead of retaining every observation and sorting them later, it keeps a carefully sampled, weighted set of representatives. As the stream grows, those representatives are compacted through levels.

For a beginner, KLL is a lesson in the difference between an exact answer and a controlled approximation. For a professional, it is a lesson in probabilistic error guarantees, weighted compaction, mergeability, distributed analytics and the danger of confusing rank error with value error.

Quick Answer

Learn KLL through quantile meaning → exact sorting cost → rank approximation → weighted levels → compaction → random parity → capacity schedule → lazy compaction → querying → merging → error bounds → distributed production use. Do not begin with a library call such as get_quantile(0.95). First understand what information the sketch deliberately throws away and what guarantee survives that loss.

1. Start With Rank, Not Percentile Vocabulary

Imagine the full stream sorted from smallest to largest. The rank of a value tells us where it lies in that sorted order. A quantile asks for the value whose rank is near a chosen fraction of the stream.

• 0.50 quantile: around the median;
• 0.90 quantile: around the 90th percentile;
• 0.99 quantile: around the 99th percentile.

If the stream has one billion values, an exact answer could require retaining and processing far more data than a monitoring system wants. A sketch changes the job: instead of exact sorted order, preserve enough information to estimate ranks within a known probabilistic error envelope.

2. The Error Is Usually About Rank

Suppose the target quantile should have rank 950,000 in a stream of one million items. A rank-error guarantee says the returned value should correspond to a rank near that target, within some tolerance.

That does not mean the numerical value itself is within the same percentage. If the distribution contains a huge jump between adjacent high-percentile values, a small rank error can correspond to a large value difference.

This distinction is essential in latency, finance, scientific measurements and reliability data. Always ask: what kind of approximation is guaranteed?

3. Exact Storage Is the Baseline You Are Compressing

The simplest exact method is conceptually easy:

1. store every item;
2. sort all items;
3. answer quantiles by indexing the sorted array.

The problem is memory and repeated work. Streaming systems may receive data continuously across many machines. KLL instead updates a bounded summary online and later combines summaries.

4. Think in Weighted Levels

A useful mental model is a stack of levels. Items in level 0 represent roughly one original observation each. Items promoted to level 1 represent more observations. Higher levels represent progressively larger weights.

If a compaction keeps roughly half the items and promotes them one level, each promoted representative now stands in for more of the original stream. The exact implementation details are sophisticated, but the central idea is simple: fewer stored items, larger statistical responsibility per retained item.

5. Compaction Is Structured Forgetting

When a level becomes too full, its items are sorted and compacted. A simplified teaching version is:

sort(level)
choose random parity: even or odd
keep every other item using that parity
promote kept items to the next level
discard the others

Why random parity? If compaction always kept the same side of each pair, the sketch could introduce systematic bias. Randomization lets positive and negative rank errors cancel probabilistically across compactions.

6. Do a Card Experiment Before Writing Code

Write 16 numbers on cards. Put them into level 0. When the level overflows, sort the cards, flip a coin, and keep either positions 0,2,4,… or 1,3,5,…. Move those kept cards to level 1 and give them twice the weight.

Repeat until several compactions have occurred. Then reconstruct an approximate weighted ordering. This physical exercise makes two professional ideas visible: retained values have different weights, and error is created at compaction events rather than at query time.

7. KLL Is More Than “Repeatedly Throw Away Half”

The KLL design from Karnin, Lang and Liberty improves the memory–accuracy trade-off through a carefully chosen capacity schedule across levels. Lower and higher levels do not all need the same capacity. Modern KLL implementations also use lazy compaction strategies so compaction work is triggered in ways that improve practical efficiency and compactness.

This is where the beginner model should yield to the professional one: the coin-flip compactor explains the mechanism, but the proven sketch depends on how level capacities, compaction choices and error accumulation interact.

8. Weighted Querying Reconstructs an Approximate Distribution

To answer a quantile query, conceptually gather retained items with their level weights, order them by value, and walk through cumulative weight until the requested rank is reached.

Libraries optimize this process, but the conceptual contract stays the same: each retained item contributes an amount of mass proportional to the number of original observations it represents.

9. The Parameter k Controls the Accuracy–Space Trade-Off

Production KLL APIs expose a parameter commonly called k. Larger k generally means more retained items, more memory and better rank accuracy. Smaller k means a smaller sketch with looser error.

Current Apache DataSketches documentation uses a default k = 200 and reports approximately 1.33% single-sided normalized rank error and about 1.65% double-sided PMF error at 99% confidence for that configuration. Those figures belong to that implementation and parameterization; do not copy them blindly into a different library or modified sketch.

10. Mergeability Is Why Sketches Matter in Distributed Systems

Suppose 100 machines each observe a shard of a data stream. Shipping every raw measurement to one coordinator defeats the point of distribution. Instead, each worker can build a local KLL sketch. The sketches are then merged and, if necessary, compacted again.

That makes the summary useful for:

• distributed telemetry;
• large analytical databases;
• stream-processing systems;
• partitioned logs;
• incremental monitoring pipelines.

Mergeability is not an afterthought. It is part of the algorithmic contract that makes streaming sketches operationally valuable.

11. Current Production Evidence Is Easy to Find

Apache DataSketches maintains KLL implementations and documentation across multiple languages. Apache Druid exposes KLL aggregators for approximate quantile, rank, PMF and CDF queries. Apache’s BigQuery integration provides KLL build and merge functions, and the DataSketches PostgreSQL extension includes KLL quantile sketches.

The professional lesson is not “use KLL everywhere.” It is that the algorithm has crossed from theory into real analytics infrastructure, so serialization format, merge semantics, parameter choices and compatibility now matter alongside asymptotic space bounds.

12. Query Semantics Need Care

A mature API may support several related questions:

• quantile: approximately which value sits at a requested rank fraction?
• rank: approximately what fraction of observations are at or below a value?
• CDF: how much mass lies below chosen split points?
• PMF/histogram: how much mass lies between split points?

Inclusive versus exclusive rank conventions can also differ. Read the library contract. Two implementations can both be correct while returning slightly different boundary behavior.

13. Compare Sketch Families by Error Contract, Not Popularity

KLL is one member of a larger design space. Greenwald–Khanna is a classic deterministic quantile summary. t-digest is often chosen when tail behavior and practical percentile estimation are central. Other sketches target relative value error, distinct counting or heavy hitters rather than rank error.

Do not ask which sketch is “best” in the abstract. Ask:

• Is the required guarantee rank error or value-relative error?
• Are merges required?
• Are extreme tails especially important?
• Must results be deterministic?
• What memory budget is available?
• Does the implementation provide compatible serialization across languages?

14. Randomness Does Not Mean Uncontrolled

KLL uses randomized compaction, but its accuracy is not simply “usually okay.” The point of the theory is to bound the probability that accumulated rank error exceeds a target. This is a central lesson in randomized algorithms: a probabilistic algorithm can have a precise reliability contract.

For testing, however, randomness still matters. Reproducible seeds are useful during debugging. Statistical tests should examine error distributions across many streams and seeds rather than only one convenient dataset.

15. Adversarial Data Shapes Matter

Test more than uniform random values. Useful cases include:

• all values equal;
• strictly increasing and decreasing streams;
• heavy duplication;
• two widely separated clusters;
• long-tailed distributions;
• rare extreme outliers;
• many merged shards with very different sizes.

The target is not only “does the median look plausible?” Measure rank error against the exact sorted data for small and medium test sets.

16. Memory Measurements Should Include Serialization

In production, in-memory object size is only one number. Also measure:

• serialized sketch size;
• merge cost;
• update throughput;
• query latency;
• allocation behavior;
• cross-version and cross-language compatibility when relevant.

A mathematically compact summary can still perform poorly if an implementation allocates excessively or repeatedly rebuilds sorted views.

17. A Better Way to Learn It

KLL is ideal for a predict–trace–modify progression. Programming-education research behind PRIMM recommends letting learners predict and investigate working code before writing from scratch. Subgoal-labelled worked examples reduce unnecessary search, while recent research on faded Parsons problems shows value in gradually restoring code-production demands after learners understand structure.

For KLL, the subgoals are: insert, detect level pressure, sort, choose compaction parity, promote weighted survivors, update size, merge levels, then answer weighted rank queries. A learner should trace those steps on paper before implementing an optimized buffer layout.

Common Failure States

• Calling KLL a value-error sketch instead of a rank-error sketch.
• Forgetting that retained items carry different weights.
• Using deterministic always-even compaction and introducing avoidable bias.
• Assuming every level has identical capacity in the proven KLL design.
• Merging sketches by concatenating samples without restoring level/weight semantics.
• Reporting a library’s default error bound without its k value and confidence convention.
• Testing only the median on friendly random data.
• Assuming two percentile libraries use identical inclusive/exclusive rank definitions.

Practice Ladder

• Beginner: compute exact ranks and quantiles from a 20-number list.
• Foundation: simulate a two-level random compactor with weighted cards.
• Intermediate: implement a small educational sketch and compare estimated ranks with exact sorted data.
• Advanced: add multiple levels, variable capacities and sketch merging.
• Professional: evaluate a mature KLL library under realistic stream shapes, shard merges and serialization constraints; report empirical rank-error distributions against documented theoretical bounds.
• Explanation test: explain why a small rank error can still correspond to a large numerical-value error in a gapped distribution.

Learning Hall Boundary

This article owns the specialist KLL quantile-sketch job: weighted compaction levels, probabilistic rank error, mergeability and streaming percentile engineering. It does not replace eduKateSengkang’s existing general streaming-algorithm article, Count-Min/HyperLogLog sketching article, probability foundations, MindOS, Bolt or Student/Studying Interface canonical jobs. Those remain separate teaching lanes.

Evidence Boundary

The foundational reference is Zohar Karnin, Kevin Lang and Edo Liberty, Optimal Quantile Approximation in Streams, FOCS 2016, DOI 10.1109/FOCS.2016.17. Current Apache DataSketches documentation describes KLL as a compact lazy-compaction quantile sketch and documents present-day accuracy conventions and APIs. Apache Druid, Apache DataSketches for BigQuery and the DataSketches PostgreSQL extension provide current production examples of KLL-based distribution estimation and sketch merging. The learning progression is informed by PRIMM, subgoal-labelled worked examples, algorithm-visualisation research and 2025–2026 work on Parsons and faded-Parsons scaffolds.

Professional rule: you understand KLL when you can state exactly what error is bounded, explain why compaction creates weighted representatives, merge sketches without changing their statistical meaning, and choose k from an accuracy–memory requirement rather than by habit.