← Back to list
AI & Data
#CountMinSketch#확률적자료구조#빈도추정#헤비히터#스트리밍
Last updated · 2026-11-09

Count-Min Sketch (Frequency-Estimation Sketch)

1. Overview

A. Definition

Count-Min Sketch (CMS) is a probabilistic data structure that approximates how many times (frequency) each element has appeared in a large data stream without keeping a per-element counter, using only a fixed-size two-dimensional counter array and several hash functions; at query time it takes the minimum (min) across the counters of several rows to suppress the overestimation caused by hash collisions.

Count-Min Sketch answers the question "how many times has this element occurred so far." Counting exactly would require a counter for every distinct key that appears, so with hundreds of millions of distinct keys the memory grows accordingly (O(number of distinct keys)). CMS does not store keys; instead it records the frequencies of many keys overlaid on a single small integer array of width w and depth d. As a result the memory stays the same whether there are ten thousand or a billion distinct keys, in exchange for a small error of overestimation caused by collisions. Unlike the earlier [[bloom-filter]], which approximates "membership," and [[hyperloglog]], which approximates "distinct count," CMS approximates "frequency (count)," so the three structures form a complementary family of probabilistic summaries (sketches).

CMS has four properties. First, memory is fixed regardless of input size or the number of distinct keys (constant space). Second, insertion and lookup each touch only d hashes and d counters, so they are very fast at O(d), where d is usually a small constant of a few to around ten. Third, two sketches that use the same width, depth, and hashes can be merged losslessly by element-wise addition, which fits distributed aggregation naturally. Fourth, with no negative updates (count increments only), the estimate is always at least the true value and never underestimates. This bundle of four properties determines the scope of CMS.

B. Background and Necessity

As web, advertising, telecom, and financial logs pour in at hundreds of thousands of events per second, frequency queries and heavy-hitter detection such as "which URL is called most," "which source IP sends an abnormally large number of packets," and "which search term is surging" have become key operational metrics. Yet exact frequency aggregation is inherently expensive. Because a counter must be maintained for every key, with hundreds of millions of distinct keys in billions of daily log entries a hash map of several to tens of GB is needed, and updating and querying it in real time turns memory pressure and GC latency directly into service cost.

Count-Min Sketch engineers around the operational reality that "a relative error within a few percent, not an exact frequency, is good enough." Whether an IP connected exactly 1,000,230 or 1,000,245 times does not affect the decision of "is this IP a heavy hitter above the threshold," so tolerating a small overestimate in exchange for saving tens to thousands of times the memory is reasonable. In particular, thanks to the decisive advantage that CMS is easy to merge, sketches aggregated separately per server, time window, or shard can be combined losslessly to recover the global frequency, which has made it a de facto standard summary structure in distributed and streaming environments.

Understanding why exact aggregation is fundamentally expensive makes the value of CMS clear. An exact frequency table must remember "every key seen so far," so if the key space is open (e.g., arbitrary strings, IPs, URLs) and the distribution is long-tailed, the number of counters explodes. In horizontally scaled environments this full state hits two walls at once: node memory limits and network shuffle cost. CMS sidesteps these walls with the insight that "if all you need is the single statistic of frequency, there is no reason to remember every key one by one," stacking many keys onto the same counters while statistically suppressing the effect of collisions.

C. Characteristics

CMS has a one-directional error structure in which it never underestimates. This is especially advantageous for detection that cannot tolerate misses (false negatives), such as "raise an alarm when a threshold is exceeded." On the other hand, even a rarely occurring key can look inflated if it collides with another frequent key, so there is a limit that estimates for sparse keys are relatively inaccurate. Also, the basic form supports only insertion and lookup; allowing deletion (negative updates) breaks the one-directional guarantee of min, so a separate variant is needed.

Structurally, CMS has a deep affinity with the [[bloom-filter]]. Where a Bloom filter sets a bit, CMS places an integer counter, generalizing "is it set" to "how much has accumulated." Indeed, reducing a counter to one bit converges to a Bloom filter, and changing the lookup from min to OR converges to a membership query. This view illustrates the design principle that "what you count and how you aggregate on top of the same hash-overlap structure determines the use of the data structure," and ties the three probabilistic summaries (Bloom, HLL, CMS) into a single conceptual framework.

2. Structure and Operating Principle

The core of Count-Min Sketch is "record one key distributed across d counters using d different hashes, and at query time trust the minimum among those d." Even if a particular counter is inflated by a collision, the probability that all d collide badly at the same time is very low, so the minimum is close to the true value. This is the same idea as measuring several times and trusting the smallest result; thanks to the one-directionality that "collisions only increase values," the minimum becomes the least-contaminated estimate.

flowchart TB
    X["input (key x, increment c)"] --> H1["hash h1(x) → column j1"]
    X --> H2["hash h2(x) → column j2"]
    X --> HD["hash hd(x) → column jd"]
    H1 --> R1["row1: C[1][j1] += c"]
    H2 --> R2["row2: C[2][j2] += c"]
    HD --> RD["rowd: C[d][jd] += c"]
    subgraph TABLE["counter array d rows x w columns"]
      R1
      R2
      RD
    end

The data structure consists of a two-dimensional integer counter array C made of d rows (depth) x w columns (width) and d mutually independent hash functions h₁…h_d. Each hash maps a key to a column index in the range [0, w). Each row is an independent "approximate frequency table," and because rows use different hashes, even if two keys collide in row 1 they usually do not collide in rows 2 and 3. It is exactly this inter-row independence that justifies trusting the minimum of the d estimates.

The Update operation Update(x, c) computes the column index hᵢ(x) for each row i (=1…d) and adds c to C[i][hᵢ(x)]. Usually c=1 each time an element arrives in the stream, but for weighted logs an arbitrary positive c can be added. Since one key touches exactly one cell in each row, the update cost is constant at O(d) regardless of input size. For example, with d=4 each event needs only 4 hashes and 4 additions, so a stream of millions per second can be handled on a single node.

The Query operation Query(x) reads C[i][hᵢ(x)] in each row and returns the minimum of those d values as the estimated frequency f̂(x). If the true frequency of a key x is f(x), then every counter where x was recorded contains at least f(x) plus the contributions of other keys, so C[i][hᵢ(x)] ≥ f(x) holds in every row. Therefore the minimum is also at least f(x), and this is the core guarantee of CMS that overestimation is possible but underestimation is impossible.

Let us solidify the intuition with a small example. Suppose a sketch with d=2, w=4 received key A 5 times, B 3 times, and C 2 times. If hash h₁ in row 1 sends A and C to the same column, that column accumulates 5+2=7, so querying A from row 1 alone overestimates by 2 at 7. But if hash h₂ in row 2 sent A to a column different from B and C, that column is exactly 5, and the query recovers the true value with min(7, 5)=5. Thus the utility of the min operation is that a collision in one row is corrected by a "clean" counter in another row, and as the number of rows d increases, the probability that all rows are contaminated at once drops exponentially, stabilizing the estimate.

3. Query-Processing Flow and Heavy-Hitter Detection

CMS alone can answer only "the frequency of a specific key" and cannot directly answer "what are the top-K frequent items." Because the most common real-world requirement is exactly heavy-hitter detection, CMS is usually used combined with a small min-heap or Top-K structure. The flow below is a typical pipeline that takes a stream element, updates the sketch, and promotes it to a candidate if its estimated frequency exceeds the heap's lower bound.

flowchart LR
    S["stream element x"] --> U["CMS.Update(x, 1)"]
    U --> Q["est = CMS.Query(x)"]
    Q --> D{"est > heap minimum?"}
    D -- "yes" --> P["reflect x, est into Top-K heap"]
    D -- "no" --> N["ignore"]
    P --> O["periodically output top-K frequent items"]
    N --> O

In this structure, CMS plays the role of "maintaining the approximate frequency of all keys in constant memory," and the heap plays the role of "selecting and keeping sorted only the top K." Since the heap size is fixed at K, total memory remains constant. For example, if a telecom carrier extracts the top 100 destination IPs per one-minute window ([[stream-processing-windowing]]), a few MB of CMS and a 100-slot heap suffice instead of an exact table of all the millions of distinct IPs. However, because of overestimation a sparse key may occasionally land in the heap wrongly, so designs that add a margin to the threshold or attach precise verification at window close are used.

A point that must be noted in heavy-hitter detection is the asymmetry that CMS captures every "candidate whose estimated frequency is at or above the threshold" (no misses), but some candidates may be false, inflated by collisions. Therefore real-world pipelines often adopt a two-stage structure of "cheaply filter first-pass candidates with CMS (100% recall), then verify with precise counters or sampling (precision correction)." This applies expensive exact aggregation to only a few candidates rather than the whole, a typical approximate-plus-precise combination pattern that captures both cost and accuracy.

Mergeability is also an important axis of the query flow. If shard A and shard B each maintained CMS_A and CMS_B, then CMS_A+B, which adds the two arrays coordinate by coordinate, is mathematically identical to "processing the entire stream with a single sketch." Thanks to this, in MapReduce- or Spark-style distributed aggregation each partition can build a local sketch and the reduce stage only needs to add them, eliminating the cost of shuffling raw data. This additivity, together with [[hyperloglog]], is the decisive property that made CMS a standard summary in distributed environments.

4. Error Bound and Parameter Design

The error of CMS is controlled not by chance but by a rigorous probabilistic upper bound. Let the total frequency sum of the entire stream (L1 norm) be N = Σf(x), and set the width to w and depth to d; then the following holds. The expected contribution of other keys mixing into the counter of key x in one row is roughly N/w (the intuition that total mass N spreads evenly across w columns). Applying Markov's inequality, the probability that the overestimation in one row exceeds εN is (N/w)/(εN) = 1/(εw). Setting the width to w = ⌈e/ε⌉ makes this probability 1/e, and since the d rows are independent, the probability that all rows simultaneously exceed εN is (1/e)^d = e^(−d). To make this at most the failure probability δ, a depth of d = ⌈ln(1/δ)⌉ suffices.

In summary, when w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, the estimate guarantees f(x) ≤ f̂(x) ≤ f(x) + εN with probability at least 1−δ, and the space is fixed at O((1/ε)·ln(1/δ)) counters. For example, if you want ε=0.001 (0.1% of total mass) and δ=0.001 (99.9% confidence), then w ≈ ⌈e/0.001⌉ = 2,719 and d = ⌈ln(1000)⌉ = 7, so with about 2,719×7 ≈ 19,033 counters (about 76KB for 4-byte integers) you can approximate the frequency of hundreds of millions of keys. The fact that memory is fixed at this level regardless of the number of distinct keys is the practical appeal of CMS.

Parameter Meaning Formula If larger/smaller
ε (epsilon) allowed error ratio (εN) input requirement smaller is more accurate, w increases
δ (delta) guarantee-failure probability input requirement smaller raises confidence, d increases
w (width) number of columns ⌈e/ε⌉ larger lowers collisions, raises memory
d (depth) number of rows/hashes ⌈ln(1/δ)⌉ larger raises confidence, raises query cost

A point that must be noted here is that the error bound is proportional to the absolute quantity εN. The larger the high-frequency stream N, the larger εN, so frequent keys (heavy hitters) have small relative error while sparse keys are buried under εN and have large relative error. This mathematically explains the trait that CMS is by design strong at heavy-hitter detection and weak at precise estimation of the tail distribution. For this guarantee to hold, the hash functions must have a property of at least pairwise independence, and in practice d hashes are constructed by giving different seeds to non-cryptographic hashes such as MurmurHash or xxHash.

5. Main Variants and Extensions

Several variants have been proposed to reduce the overestimation of basic CMS or to broaden its functionality, and each differs in "what it gives up and what it gains." Rather than simply listing variants, understanding why each variant is needed is the key to design judgment.

Conservative Update (CU) is the technique that reduces overestimation the most in practice. Instead of raising all d counters on update, it first finds the minimum m among the current d values and raises only the counters whose value is m by c. Since the query looks at the minimum anyway, not raising "already-large-enough counters" does not harm the estimate, and by suppressing unnecessary increments the average error drops greatly. The cost is that deletion becomes impossible (the guarantee collapses under negative updates) and the added minimum computation makes updates slightly slower. As of 2024, precise analyses of the worst-case and average error of conservative updates are still being published, so it remains a variant actively researched even theoretically.

Count Sketch is a cousin structure proposed before CMS; it additionally assigns each key a ±1 sign hash besides the column index, adds ±c to the counter on update, and takes the median of the d estimates at query time. Because the signs cancel out, the effect of collisions converges to 0 on average, giving an unbiased estimate, and the error is proportional to the L2 norm rather than L1 (N), which can be more favorable for skewed streams. It also supports negative updates (deletion). In exchange, the sign hash and median computation make implementation more complex, and the one-directional guarantee of CMS that "it never underestimates" disappears. The table below summarizes the difference in roles of the three probabilistic summaries.

Structure Question answered Error direction Deletion Representative metric
[[bloom-filter]] membership (present?) false positives only impossible (basic) FPP
[[hyperloglog]] distinct count (how many kinds?) both directions impossible relative error ~2%
Count-Min Sketch frequency (how many times?) overestimation only impossible (basic) εN, δ
Count Sketch frequency (how many times?) both directions (unbiased) possible L2-based

Beyond these, variants that compress the variable increment on a log scale to save even more memory, a decay CMS that attenuates old frequencies over time, and a sliding-window CMS that keeps a CMS per window and aggregates only the recent interval are widely used in streaming analytics. Whichever variant is chosen, the key is that it is a different answer to the common question "how to handle collisions."

Variant selection is ultimately a triangular trade-off of error, functionality, and cost. When accuracy matters most and there is no deletion, conservative update is the default; when deletion or unbiased estimation is needed, Count Sketch; for real-time trends, decay or sliding windows are layered on—assembling the structure backward from the requirements. An important design principle is that changing a once-fixed width, depth, hash, or sign scheme breaks merge compatibility with existing sketches, so variants and parameters must be fixed carefully with an eye on the service lifecycle.

6. Application Cases

Network monitoring and DDoS detection is a classic use of CMS. Routers and firewalls must find "sources sending abnormally large traffic" among millions of packets per second, but there is not enough memory to keep a counter for every IP. By approximating the packet count of source IPs with CMS and promoting only heavy hitters above the threshold to ACL and [[rate-limiting]] targets, line-rate detection is possible with a few MB of memory. Because there is no underestimation, the point that there is no risk of missing attack traffic fits security detection especially well.

Database query optimization is also an important case. To estimate the selectivity of joins and filters, the optimizer needs the frequency distribution of column values. Maintaining an exact histogram of all values is expensive, so CMS is used to approximate the occurrence frequency of specific values to estimate "roughly how many result rows this condition yields" and choose an execution plan. Even approximate, it is sufficient for relative comparison, and the fact that the memory budget is fixed keeps the cost of statistics collection under control.

Cache eviction policy has Caffeine's W-TinyLFU as a representative. As seen in [[caching-strategy]], to protect "frequently used items," LFU must know each item's access frequency, but an exact frequency table of millions of keys can grow larger than the cache itself. W-TinyLFU approximates access frequency with CMS and adds time decay, combining LRU's recency and LFU's frequency to achieve a high hit rate with little memory. In fact, Caffeine shows an edge over Guava in hit rate and throughput, and its foundation is CMS-based frequency estimation.

Financial fraud and recommendation systems also rely on frequency approximation. Card companies must watch in real time whether "an abnormally large number of approval attempts concentrate at the same merchant or terminal in a short time," but updating and querying exact counters for tens of millions of merchants at millisecond granularity is hard. By approximating attempt frequency per merchant, terminal, and card BIN with CMS and routing those above the threshold to additional authentication or holds, processing is done in constant memory without missing suspicious transactions, since there is no underestimation. Recommendation systems also approximate the popularity frequency of items and search terms with CMS for popularity correction and deduplication, and since relative ranking matters more than exact numbers, approximation error is not a practical problem.

On the streaming-analytics platform and productization side, Redis is representative. Redis's probabilistic data structure module provides Count-Min Sketch as a first-class type, creating a sketch with CMS.INITBYDIM (specifying width and depth directly) or CMS.INITBYPROB (specifying target ε and δ), updating multiple items at once with CMS.INCRBY, returning estimated frequencies with CMS.QUERY, and supporting the merge of multiple sketches with CMS.MERGE. Thus workloads such as "real-time surging search terms," "approximate view counts per product," and "estimated call volume per API key" are processed in constant memory without application code changes. Large-scale analytics libraries (e.g., sketch libraries in the Spark ecosystem) also use the CMS and Count Sketch families as basic tools for frequent-item estimation.

7. Deep Dive — Design Points and Recent Trends in Practical Application

When putting CMS into a real system, it does not end with theoretical formulas but requires tuning matched to the operational context. First, the habit of back-calculating ε and δ from the "desired absolute error" is important. Since the error bound is εN, for a service where the stream total N grows to billions per day, ε must be set small enough to yield usable estimates even for sparse keys. Conversely, if "knowing just the top few heavy hitters is enough," setting ε loosely to save memory is reasonable. That is, the trade-off between required precision and memory budget must be designed explicitly in line with the business question.

Second, decay and windowing are almost always needed. Pure CMS counts only cumulative frequency, so "popularity from long ago" remains forever. To see surges and real-time trends, you must reset the sketch periodically, apply exponential decay, or aggregate only the recent interval with a sliding window. This is the point where it combines with the time semantics of [[stream-processing-windowing]], a design decision that defines "the frequency over what period you look at."

Third, the choice of overestimation-mitigation technique. When accuracy matters, adopt conservative update (CU) by default to lower the average error, but for workloads needing deletion (e.g., decrementing at session end) use a structure that supports negative updates like Count Sketch instead of CU. As of 2024, with new analyses of the error characteristics of conservative updates being published, the CMS family continues to advance in the direction of "taming collisions and errors better." Also, recently a hybrid design is being researched in which CMS combines frequency estimation with a learned model (learned sketch), pulling frequent keys into separate exact counters and leaving only sparse keys to the sketch to lower overall error.

Fourth, the security and privacy perspective is also rising. When CMS aggregates user behavior frequency, the property of not storing individual items is privacy-friendly, but because sensitive information might be inferred in reverse from estimation alone due to collisions, research on combining differential-privacy (DP) noise into the sketch is underway. This connects to the recent trend of trying to handle "aggregation utility and privacy" simultaneously.

Fifth, observability and verification must be included in the design. An approximate structure is hard to trust unless "how wrong the current estimate can be" is visible. Therefore, in operation it is desirable to constantly compute the current error bound εN from the total N and width w and expose it on a dashboard, and to monitor the actual overestimation range by periodically comparing a few keys against exact counters. Reducing "the quality of the approximation to a measurable metric" this way allows re-tuning parameters early when traffic characteristics change and error grows.

8. Considerations and Implications

First, judging applicability (application strategy). CMS is optimal when you want to know "frequency/heavy hitters in constant memory, without underestimation." Conversely, when you need an exact frequency table (settlement, billing), want a distinct count ([[hyperloglog]]), or need only membership ([[bloom-filter]]), a different tool fits. From the professional-engineer perspective, the core is the design ability to first decompose "is the requirement accuracy or approximation-tolerant, is the question frequency or cardinality" and then map the data structure.

Second, error directionality and safety design (trade-off). CMS's one-directional overestimation gives the fail-safe of "no misses in detection," but at the same time causes false positives. In areas where false-alarm cost is high, such as DDoS blocking and fraud detection, false positives must be controlled by combining threshold margins, second-pass precise verification, and conservative update. Looking at the direction of error together with the cost structure is key to operational stability.

Third, alignment with distributed/streaming architecture (related technology). CMS's additive mergeability meshes naturally with distributed processing such as MapReduce, Spark, and Kafka Streams. The pattern of each partition building a local sketch and adding at reduce eliminates shuffle cost and, combined with [[stream-processing-windowing]] and decay, composes a real-time trend pipeline. The fact that data-structure choice leads directly to architecture cost structure must be reflected early in design.

Fourth, parameter governance and reproducibility (operations/outlook). Parameters such as w, d, hash seeds, and decay period are hard to change once set, because of merge compatibility. Since sketches with different settings cannot be combined, at the organizational level the sketch settings must be standardized and version-controlled, with a migration strategy in place for changes. As an outlook, with learned sketches, differential-privacy combination, and hardware acceleration (line-rate processing) broadening the scope of CMS, its value as a standard summary structure for large-scale real-time analytics will persist.

References


In one line: Count-Min Sketch stacks frequencies overlaid in a 2D counter array using d hashes and takes the minimum at query time, approximating frequency and heavy hitters without underestimation in constant memory independent of the number of distinct keys.