CMS (Count-Min Sketch) Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])

Introduction

ExDataSketch.CMS estimates how many times each item has occurred in a stream, without keeping a counter per distinct item. Every item is hashed by depth independent hash functions into depth rows of a width-wide counter grid, incrementing one counter per row. To read a count back out, take the minimum across that item's depth counters -- collisions from other items can only push a counter up, never down, so the true count is never above what you stored, and the minimum is the row least corrupted by collisions:

flowchart LR
    A[item] --> B["depth hash functions"]
    B --> C["row 1: counters[h1] += 1"]
    B --> D["row 2: counters[h2] += 1"]
    B --> E["... row depth"]
    C --> F["estimate(item) =\nmin across rows"]
    D --> F
    E --> F

Use it for: "how many times did X occur" at a key cardinality too large to keep an exact counter per key -- rate limiting, traffic/error frequency analytics, or as a cheap pre-filter before a more expensive exact lookup for candidates that look frequent.

Don't use it for: anything where over-counting is unacceptable (billing, quotas that must never trigger early -- use an exact counter map), membership testing ("have I seen X at all" -- see ExDataSketch.Bloom), or extracting the top-K most frequent items directly -- ExDataSketch.FrequentItems and ExDataSketch.MisraGries are purpose-built for that and track which items are heavy, not just counts.

What it buys you: CMS estimates are always over-estimates, never under, and the error shrinks as width/depth grow. At the library's default width: 2048, depth: 5, error is bounded by e * N / width (e is Euler's number, N the total count seen) with probability at least 1 - (1/2)^depth -- about 0.13% of N, ~97% of the time -- in a fixed ~40 KB regardless of how many distinct keys exist:

Approach	Memory (any key cardinality)	Per-item error
Exact counter map	Grows with distinct key count	0
`ExDataSketch.CMS` (2048x5)	~40 KB, fixed	<=0.13% of N, ~97% conf.

If a small, one-sided error is acceptable in exchange for memory that doesn't grow with your key space, CMS is the standard tool for approximate frequency counting.

Sample data (cached locally)

2,000,000 page-view events over 10,000 distinct pages, power-law distributed (a few pages get most of the traffic, a long tail gets almost none) -- realistic for request/error/page-view frequency data, and the skew is exactly what makes frequency estimation interesting.

events = ExDataSketch.SampleData.cms_events()
true_counts = Enum.frequencies(events)
IO.puts("#{length(events)} events across #{map_size(true_counts)} distinct pages")

Basic usage

alias ExDataSketch.CMS

sketch = CMS.new() |> CMS.update("page_1") |> CMS.update("page_1") |> CMS.update("page_2")
CMS.estimate(sketch, "page_1")

update/3 also accepts an explicit increment (useful when you're replaying pre-aggregated counts rather than raw events):

CMS.new() |> CMS.update("page_1", 5) |> CMS.estimate("page_1")

For a batch like our sample data, update_many/2 is far more efficient than calling update/2 in a loop -- but the backend matters far more than the batching does. ExDataSketch.CMS.new/1 defaults to the Pure Elixir backend regardless of whether the Rust NIF is installed -- you always have to opt in explicitly with backend: ExDataSketch.Backend.Rust. Measured on this tutorial's hardware, update_many/2 over 500,000 events (width: 2048, depth: 5) took 26.7s on Pure vs 39ms on the Rust NIF backend -- a ~679x speedup. Every CMS.new/1 call below passes backend: ExDataSketch.Backend.Rust for exactly this reason; drop it (or fall back to Pure when ExDataSketch.Backend.Rust.available?/0 is false, e.g. no precompiled NIF for your platform) and these cells will still work, just dramatically slower on the full 2,000,000-event sample.



[{top_page, top_true_count} | _] = Enum.sort_by(true_counts, fn {_, c} -> -c end)
IO.puts("#{top_page}: true count=#{top_true_count}")

sketch = CMS.new(backend: ExDataSketch.Backend.Rust, width: 2048, depth: 5) |> CMS.update_many(events)
estimate = CMS.estimate(sketch, top_page)

IO.puts("CMS estimate=#{estimate}")
IO.puts("Sketch size: #{CMS.size_bytes(sketch)} bytes (fixed, regardless of distinct pages)")

Accuracy: over-estimation only, and where it shows up

CMS never under-counts. Check every distinct page and confirm the estimate is always >= the true count, and see where the error actually lands (the least-popular pages, which get squeezed by hash collisions with the many popular ones sharing the same width x depth grid):

results =
  for {page, true_count} <- true_counts do
    estimate = CMS.estimate(sketch, page)
    {page, true_count, estimate, estimate - true_count}
  end

never_undercounts? = Enum.all?(results, fn {_, _, _, diff} -> diff >= 0 end)
IO.puts("Every estimate >= true count: #{never_undercounts?}")

worst = Enum.max_by(results, fn {_, _, _, diff} -> diff end)
IO.puts("Worst over-estimate: #{inspect(worst)}")

avg_error =
  results |> Enum.map(fn {_, true_c, est, _} -> (est - true_c) / max(true_c, 1) end) |> Enum.sum()
avg_error = avg_error / map_size(true_counts) * 100
IO.puts("Average relative over-estimate: #{Float.round(avg_error, 2)}%")

Both numbers can look alarming at first glance -- a worst-case estimate in the tens of thousands for a page with a true count in the hundreds, and an average relative error well over 100%. Neither indicates a bug: the worst result is the extreme of ~10,000 independent queries, each with an independent ~e^-depth chance of exceeding the typical error bound, so finding one outlier among that many is expected, not anomalous. And the average is dominated by tail pages whose true count is tiny (1-50): a few hundred counts of fixed hash-collision noise (~total_events / width per row) is negligible against page_1's true count of 20,207, but enormous as a percentage of a true count of 5. The "Sizing" section below shows this shrinking directly as width/depth grow.

Sizing: width/depth trade-off

width controls per-row collision rate, depth controls how many independent rows vote (taking the minimum across rows is what caps the over-estimation) -- more of either means more memory and less error.

Each {width, depth} combination independently rebuilds a sketch from all 2,000,000 events. Each build already uses the Rust backend (see the note in "Basic usage" -- that's the ~679x speedup that makes rebuilding from scratch three times even feasible in a tutorial); Task.async/1 runs the three builds concurrently on top of that for a further, smaller win:

{top_page, top_true} = Enum.max_by(true_counts, fn {_, c} -> c end)

tasks =
  for {width, depth} <- [{256, 3}, {1024, 5}, {4096, 7}] do
    Task.async(fn ->
      s = CMS.new(backend: ExDataSketch.Backend.Rust, width: width, depth: depth) |> CMS.update_many(events)
      {width, depth, CMS.size_bytes(s), CMS.estimate(s, top_page)}
    end)
  end

for {width, depth, size_bytes, est} <- Task.await_many(tasks, :infinity) do
  IO.puts(
    "width=#{width}, depth=#{depth} (#{size_bytes} bytes): " <>
      "top page true=#{top_true}, estimate=#{est}"
  )
end

Merging

Simulating two independent workers means two independent update_many/2 calls, each over a million events -- exactly the kind of work Task.async/1 is for:

half = div(length(events), 2)
{first_half, second_half} = Enum.split(events, half)

[worker_a, worker_b] =
  [first_half, second_half]
  |> Enum.map(fn chunk ->
    Task.async(fn -> CMS.new(backend: ExDataSketch.Backend.Rust, width: 2048, depth: 7) |> CMS.update_many(chunk) end)
  end)
  |> Task.await_many(:infinity)

merged = CMS.merge(worker_a, worker_b)
{top_page, top_true} = Enum.max_by(true_counts, fn {_, c} -> c end)
IO.puts("Merged estimate for #{top_page}: #{CMS.estimate(merged, top_page)} (true: #{top_true})")

Serialization

binary = CMS.serialize(sketch)
{:ok, restored} = CMS.deserialize(binary)
IO.puts("Round-tripped estimate: #{CMS.estimate(restored, top_page)}")

When CMS isn't the right tool

CMS answers "what's the count for this specific item?" -- it has no way to tell you which items are the heavy hitters without probing every candidate individually. If you need "give me the top-K items," use ExDataSketch.FrequentItems or ExDataSketch.MisraGries instead -- see livebooks/sketches/frequent_items.livemd and livebooks/sketches/misra_gries.livemd.