Count-Min Sketch, Top-K, and t-digest for Frequency, Heavy Hitters, and Quantiles

Learning outcomes

AtlasMart operations now asks three different streaming questions: “how often did product X appear?”, “which products are the heavy hitters?”, and “what is p95 checkout latency?” No single probabilistic structure answers all three correctly.

1. Match the question to the sketch

Approximation is not one generic property. Count-Min errors, HeavyKeepers ranking behavior, and t-digest quantile error are different models and must be validated differently.

2. Count-Min Sketch: size from error and inflation probability

CMS.INITBYPROB key error probability derives width and depth from two tolerances. Redis describes error as a fraction of total counted items affecting estimate error and probability as the desired probability for inflated counts. Smaller tolerances consume more memory/CPU.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:cms:productsdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INITBYPROB atlasmart:ch11:cms:products 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INFO atlasmart:ch11:cms:products

3. CMS.INCRBY and CMS.QUERY are approximate frequency operations

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INCRBY atlasmart:ch11:cms:products p1001 20 p1002 9 p1003 4 p1004 1docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.QUERY atlasmart:ch11:cms:products p1001 p1002 p1003 p1004 p9999docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INFO atlasmart:ch11:cms:productsdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:cms:products

On this tiny fixture estimates may match exact values. Do not infer exactness. For production evaluation, generate a deterministic stream, maintain a local Counter, then compare Redis estimates to exact frequencies across head and tail items.

4. CMS merges require identical width and depth

CMS.MERGE requires the destination to be initialized and all sketches to have the same width/depth. Optional weights multiply source sketches. In Cluster, all keys for the multi-key merge need compatible slot locality.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:{ch11cms}:a atlasmart:{ch11cms}:b atlasmart:{ch11cms}:mergeddocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INITBYPROB atlasmart:{ch11cms}:a 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INITBYPROB atlasmart:{ch11cms}:b 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INITBYPROB atlasmart:{ch11cms}:merged 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INCRBY atlasmart:{ch11cms}:a p1001 10docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INCRBY atlasmart:{ch11cms}:b p1001 5docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.MERGE atlasmart:{ch11cms}:merged 2 atlasmart:{ch11cms}:a atlasmart:{ch11cms}:bdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.QUERY atlasmart:{ch11cms}:merged p1001

5. Wrong CMS use: exact money, inventory, or quotas

Frequency sketches are useful for telemetry and candidate detection, not authoritative money or stock. Hash collisions can inflate estimates. Use exact counters/ledgers for contractual values, with CMS as an observability or preselection layer.

6. Top-K tracks heavy hitters, not every exact rank

Redis Top-K uses a HeavyKeepers-style algorithm: counters plus decay and a heap of the current K candidates. It is designed to keep “elephant” flows while suppressing “mouse” noise. TOPK.RESERVE controls K, width, depth, and decay.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:topk:productsdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.RESERVE atlasmart:ch11:topk:products 3 64 7 0.9docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.ADD atlasmart:ch11:topk:products p1001 p1001 p1001 p1001 p1002 p1002 p1002 p1003 p1003 p1004 p1005 p1001 p1002docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.INFO atlasmart:ch11:topk:productsdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.LIST atlasmart:ch11:topk:products WITHCOUNTdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.QUERY atlasmart:ch11:topk:products p1001 p1004

TOPK.ADD can return an item that was expelled from the Top-K list, which is useful for change detection. The ranked list remains approximate.

7. TOPK.COUNT is deprecated and its semantics differ from CMS

The current command reference marks TOPK.COUNT deprecated as of Bloom 2.4 and notes that its counts are not higher than real counts and will likely be lower. Prefer TOPK.LIST ... WITHCOUNT for the maintained top candidates and use CMS when your main question is per-item frequency.

8. t-digest estimates quantiles and CDFs

A quantile asks for a value below which a target fraction of observations falls. A cumulative distribution function (CDF) asks for the fraction at or below a candidate value (with Redis t-digest’s documented half-weight treatment for exact equals). t-digest stores centroids rather than the full sorted sample.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:tdigest:checkoutdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.CREATE atlasmart:ch11:tdigest:checkout COMPRESSION 100docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.ADD atlasmart:ch11:tdigest:checkout 18 21 19 23 22 24 25 20 28 31 26 27 35 29 30 42 38 33 40 55docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.QUANTILE atlasmart:ch11:tdigest:checkout 0.5 0.9 0.99docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.CDF atlasmart:ch11:tdigest:checkout 30 40 50docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.INFO atlasmart:ch11:tdigest:checkout

Redis documents exact minimum/maximum results at quantiles 0 and 1; interior quantiles are estimates. A small fixture can look exact—benchmark tails on representative distributions before trusting p99 decisions.

9. Compression is an accuracy-memory control, not “percent accuracy”

TDIGEST.CREATE ... COMPRESSION n controls centroid capacity and the memory/accuracy tradeoff. Redis uses 100 as the default/common value and documents 1000 as more accurate. Do not interpret compression=100 as 100% accuracy. Use TDIGEST.INFO to observe compression, capacity, merged/unmerged nodes, observations, compression count, and allocated memory.

10. t-digest merges support distributed/sharded summaries

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:{ch11td}:a atlasmart:{ch11td}:b atlasmart:{ch11td}:alldocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.CREATE atlasmart:{ch11td}:a COMPRESSION 100docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.CREATE atlasmart:{ch11td}:b COMPRESSION 100docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.ADD atlasmart:{ch11td}:a 10 20 30docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.ADD atlasmart:{ch11td}:b 40 50 60docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.MERGE atlasmart:{ch11td}:all 2 atlasmart:{ch11td}:a atlasmart:{ch11td}:bdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.QUANTILE atlasmart:{ch11td}:all 0.5 0.95

If the destination exists, merge semantics differ with OVERRIDE. When no explicit compression is supplied, Redis chooses compression according to source/destination rules documented by TDIGEST.MERGE. Record that policy in production code.

11. Exact ground truth for frequency, heavy hitters, and quantiles

from collections import Counterfrom math import ceil# Deterministic AtlasMart fixture. Redis is not involved in this exact baseline.events = [    "u01","u02","u03","u01","u04","u05","u02","u06","u01","u07",    "u08","u09","u10","u03","u11","u12","u13","u01","u14","u15",]exact_unique = len(set(events))exact_freq = Counter(events)print("exact unique:", exact_unique)print("u01 exact frequency:", exact_freq["u01"])print("top exact:", exact_freq.most_common(5))# For a quantile ground truth, pick an explicit rank convention and document it.latencies = sorted([18,21,19,23,22,24,25,20,28,31,26,27,35,29,30,42,38,33,40,55])def nearest_rank(q):    i=max(0,min(len(latencies)-1,ceil(q*len(latencies))-1))    return latencies[i]for q in (0.5,0.9,0.99):    print(q, nearest_rank(q))

12. Tail validation needs many trials and a stated quantile convention

“p99” can mean different finite-sample rank/interpolation conventions in different tools. Before comparing t-digest to an exact library, state the exact-ground-truth convention. Then evaluate absolute/relative quantile error at p50/p90/p95/p99/p99.9 across realistic skew/outliers, not just one tiny monotonic list.

13. Persistence/security version note

Redis 8.10.1 contains security fixes for Count-Min Sketch RDB loading and Top-K cleanup. That is operationally relevant because these sketches are persisted and restored. Pin patch versions, validate backups/restores, and treat untrusted RDB files as sensitive input rather than assuming probabilistic structures are harmless metadata.

14. Cleanup

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:cms:products atlasmart:{ch11cms}:a atlasmart:{ch11cms}:b atlasmart:{ch11cms}:merged atlasmart:ch11:topk:products atlasmart:ch11:tdigest:checkout atlasmart:{ch11td}:a atlasmart:{ch11td}:b atlasmart:{ch11td}:all

15. Production judgment

CMS is for approximate point frequency, Top-K for the dominant candidates, and t-digest for distribution quantiles. Benchmark the question you actually care about: per-item estimate error, precision/recall of top-K membership, or quantile error at specified tails. Include memory, ingestion throughput, p95/p99 command latency, merge costs, Cluster co-location, restore behavior, ACLs, and patch-version security in the decision.

16. Summary and next step

Three sketches answer three distinct questions with distinct error models. Lesson 5 assembles the whole chapter into a decision framework: when is approximation an engineering win, and when is exactness part of correctness?

Authoritative references

• Redis probabilistic data types — current integrated probabilistic data-structure overview
• Redis data types — current Redis data-type surface
• HyperLogLog — cardinality-estimation model and operations
• PFADD — HyperLogLog insertion semantics
• PFCOUNT — standard error, memory, and union-count semantics
• PFMERGE — persistent HLL union/merge semantics
• Bloom filter — Bloom membership model and examples
• BF.RESERVE — capacity, false-positive rate, scaling, and memory formulas
• BF.INFO — Bloom capacity/filter/memory evidence
• Cuckoo filter — Cuckoo membership/deletion tradeoffs
• CF.DEL — safe deletion requirement and corruption warning
• CF.COUNT — Cuckoo multiplicity estimate semantics
• Count-Min Sketch — frequency-estimation model
• CMS.INITBYPROB — error/probability sizing controls
• CMS.MERGE — same-dimension merge and weights
• Top-K — HeavyKeepers-based heavy-hitter model
• TOPK.LIST — ranked top-k output and WITHCOUNT
• TOPK.COUNT — deprecated count command and undercount note
• t-digest — percentile/CDF model and merge operations
• TDIGEST.CREATE — compression versus memory/accuracy tradeoff
• TDIGEST.QUANTILE — quantile estimate semantics
• TDIGEST.INFO — observations, nodes, compression, memory evidence
• Probabilistic command compatibility — current command/Redis product compatibility matrix
• Redis 8.0 release notes — integrated probabilistic features and ACL-category change
• Redis 8.10 release notes — 8.10.1 security baseline for CMS/Top-K