# Count-min sketch > A count-min sketch estimates how often a key appears in a stream without storing a counter for every key. It trades exact counts for a fixed-size table of counters, making it useful for high-cardinality traffic analysis and approximate hot-key detection. Source: https://sysround.com/concepts/count-min-sketch Updated: 2026-11-05 ## How count-min sketch works Allocate a table with d rows and w counters per row, initially zero. Each row has its own hash function that maps a key to one column; the sketch stores counters, not the original keys. For each event, hash its key once per row and increment the selected counters. For example, a request for /products/42 increments one counter in each of five rows; processing costs O(d), regardless of how many distinct URLs appear. To estimate a key's frequency, read its selected counter in every row and return the minimum. If those counters contain 108, 103, 117, 105, and 110, return 103. Collisions add other keys' traffic to these counters, so with nonnegative updates and no counter overflow, the estimate cannot be below the true count. Choose width w = ceil(e/epsilon) and depth d = ceil(ln(1/delta)). With suitable independent hash functions, a fixed key's estimate is at most its true frequency plus epsilon times the total stream count N, with probability at least 1 - delta. This is an additive error bound, not a percentage of that key's count, and the probability guarantee is per query rather than automatically simultaneous across every key. For distributed aggregation, add corresponding counters from sketches that use identical dimensions and hash functions. The merged sketch represents the combined input streams; overlapping events and replayed messages still get counted more than once unless the processing pipeline prevents that. For recent traffic, keep separate sketches in time buckets, merge the active buckets, and discard expired buckets. This approximates a sliding window at bucket boundaries and requires an explicit policy for late events. Because the sketch cannot enumerate keys, finding top items also requires a bounded candidate set or a separate heavy-hitter algorithm. ## Worked example: Estimating hot URL frequencies in one minute Suppose a service processes 1,000,000 requests per minute and needs approximate URL frequencies for cache-admission decisions. Choose epsilon = 0.001 and delta = 0.001: the sketch needs 2,719 columns and 7 rows. With 64-bit counters, that is about 149 KiB per minute bucket, excluding metadata. For a fixed URL, its estimate never undercounts and exceeds its true count by at most 1,000 with probability at least 99.9%, under the standard assumptions. That may distinguish a URL receiving 50,000 requests from cold traffic, but it cannot reliably distinguish counts of 20 and 200. Keep a separate candidate structure to identify URLs worth querying; the sketch alone cannot list them. ## Trade-offs - **Fixed memory versus exact counts.** The table size does not depend on the number of distinct keys, but collisions inflate estimates and can overwhelm the true counts of rare keys. - **Accuracy versus memory and CPU.** Reducing epsilon requires more columns, while reducing the failure probability requires more rows and therefore more work per update and query. - **Frequency lookup versus key discovery.** A sketch can estimate a supplied key's frequency but cannot list keys or produce top K without another data structure. - **Easy merging versus delivery correctness.** Compatible sketches merge by counter addition, but this provides neither deduplication nor protection against double-counting overlapping snapshots. - **Lifetime counts versus recent activity.** A basic sketch never forgets events, so windowed counts need extra sketches, expiration rules, and memory proportional to the number of retained buckets. - **Approximate signals versus authoritative decisions.** Overestimation can be acceptable for cache admission or traffic exploration but can wrongly reject requests or misstate totals if used for strict quotas or billing. ## When to use it in a system design interview - The input contains too many distinct URLs, item IDs, or metric labels to maintain an exact in-memory counter for every key. - The requirement is approximate event frequency or heavy-hitter detection, not distinct-user counting or an exact leaderboard. - You need compact summaries that workers can merge without sending every per-key count to a central service. - The interviewer allows bounded counting error, and you can express an acceptable absolute error relative to the total events in each window. ## How to bring it up in the interview - Start with the requirement: explain why an exact hash map exceeds the memory budget and why approximate frequencies are sufficient. - State the one-sided error and its scope: for nonnegative updates, collisions only inflate counts, and the probabilistic upper bound is additive in total stream volume. - Size the table using epsilon, delta, counter width, and the number of active windows; expect questions about rare keys, counter overflow, and per-query versus whole-system guarantees. - For top K, explain candidate discovery separately from frequency estimation; expect the interviewer to probe whether your candidate strategy can miss a winner and whether exact ranking is required. - Describe compatible hash seeds, disjoint input partitions, checkpoint recovery, and late-event handling before claiming that distributed merging is straightforward. ## Common mistakes - Saying the sketch has 1% relative error for every key; its usual bound is an additive fraction of the entire stream's count. - Claiming that a count-min sketch alone returns the most frequent keys, even though it does not retain their identities. - Using it to count distinct users; repeated events increase frequency rather than deduplicating users. - Assuming that merging sketches removes duplicate deliveries or that a lifetime sketch automatically represents a sliding window. - Adding arbitrary negative updates while continuing to claim the standard nonnegative-stream guarantees. ## Interview questions where it comes up - [Design a top K trending system](https://sysround.com/questions/design-top-k): It is a central approximate-frequency option to evaluate alongside candidate tracking, while explaining why it cannot satisfy an exact distributed top-K requirement. - [Design a metrics monitoring system like Datadog](https://sysround.com/questions/design-metrics-monitoring-system): It supports bounded-memory estimates of frequent metric labels or series when identifying which sources dominate high-cardinality ingestion. - [Design Google Analytics](https://sysround.com/questions/design-google-analytics): It supports approximate per-page or per-event frequencies over high-cardinality traffic, separately from distinct-user estimation and exact funnel calculations. ## FAQ ### What is the error bound of a count-min sketch? For nonnegative updates, the estimate is never below the true frequency, assuming counters do not overflow. With width ceil(e/epsilon) and depth ceil(ln(1/delta)), a fixed key's estimate is at most its true frequency plus epsilon times the total stream weight with probability at least 1 - delta. Rare keys can therefore have large relative errors. ### Can a count-min sketch find the top K items? Not by itself, because it stores counters rather than item identities. Pair it with a candidate-tracking strategy, or consider a heavy-hitter algorithm such as Space-Saving. If the requirement is exact top K, especially as windowed scores decrease, an approximate sketch is not a substitute for exact aggregation and ranking. ### How is count-min sketch different from Bloom filters and HyperLogLog? A count-min sketch estimates how often a supplied key appears. A Bloom filter answers approximate set-membership queries, while HyperLogLog estimates the number of distinct keys. Choose based on whether the question asks about frequency, membership, or cardinality. ## Related concepts - [Hot keys and hot partitions](https://sysround.com/concepts/hot-keys) - [Stream processing](https://sysround.com/concepts/stream-processing) - [Windowing and watermarks](https://sysround.com/concepts/windowing) - [HyperLogLog](https://sysround.com/concepts/hyperloglog) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.