FrequentItems Tutorial

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

Introduction

ExDataSketch.FrequentItems implements SpaceSaving: at most k counters, each tracking one candidate item. A tracked item just increments its counter. A new item takes a free slot if one exists; once all k slots are full, the new item evicts whichever tracked item currently has the lowest count, inheriting that count plus one -- and remembers the evicted count as its error bound. Frequent items naturally survive (their counts stay high enough to never be the minimum); items that showed up once and never again get evicted almost immediately:

flowchart LR
    A[item] --> B{"already\ntracked?"}
    B -->|yes| C["count += 1"]
    B -->|no| D{"free slot\n(< k tracked)?"}
    D -->|yes| E["insert,\ncount = 1"]
    D -->|no| F["evict min-count entry,\nreplace: count = min+1,\nerror = min"]

Unlike ExDataSketch.CMS, which answers "what's the count for this item" and requires you to already know which items to ask about, FrequentItems directly hands you the ranked list.

Use it for: top-K questions directly -- "what are the trending search terms," "which endpoints get the most traffic" -- where you want the ranked list itself, not just a count for items you already suspect are hot.

Don't use it for: point queries on arbitrary items ("what's the count for this specific item," whether or not it's a heavy hitter -- ExDataSketch.CMS is simpler and cheaper for that); data with no real heavy hitters (SpaceSaving's error bound is only tight when a few items dominate; near-uniform frequency data gives you a ranked list with a much looser guarantee); an exact top-K list with zero error tolerance -- use a full counter map and sort it.

What it buys you: memory is bounded by k, not by how many distinct keys the stream actually contains. A k: 100 sketch over 1,000,000 queries drawn from 5,000 distinct terms measured ~2.9 KB -- and critically, that number doesn't change if the distinct-term count were 5 million instead of 5,000, unlike an exact counter map:

Approach	Memory (any distinct-key count)	What you get
Exact counter map	Grows with distinct key count	Every key's exact count
`ExDataSketch.FrequentItems` (k=100)	~2.9 KB, fixed	Top-K ranked list, error-bounded

Sample data (cached locally)

1,000,000 search queries over 5,000 distinct terms, power-law distributed -- a handful of terms dominate, most appear rarely.

queries = ExDataSketch.SampleData.frequent_items_queries()
true_counts = Enum.frequencies(queries)
IO.puts("#{length(queries)} queries across #{map_size(true_counts)} distinct terms")

Basic usage

alias ExDataSketch.FrequentItems

sketch = FrequentItems.new(k: 100) |> FrequentItems.update_many(queries)

sketch |> FrequentItems.top_k() |> Enum.take(5)

Each entry is a map with :item, :estimate, :error (max possible overcount), :lower, and :upper -- SpaceSaving's guarantee is that the true count always falls in [lower, upper]:

top_5 = FrequentItems.top_k(sketch) |> Enum.take(5)

for entry <- top_5 do
  true_count = Map.get(true_counts, entry.item, 0)
  in_bounds = entry.lower <= true_count and true_count <= entry.upper

  IO.puts(
    "#{entry.item}: estimate=#{entry.estimate}, true=#{true_count}, " <>
      "bounds=[#{entry.lower}, #{entry.upper}], true in bounds: #{in_bounds}"
  )
end

frequent/2: items above an absolute count threshold

frequent = FrequentItems.frequent(sketch, 50_000)
IO.puts("#{length(frequent)} terms with a guaranteed count >= 50,000")

Sizing: k trade-off

More counters means more of the long tail gets tracked accurately before being evicted:

for k <- [5, 20, 100] do
  s = FrequentItems.new(k: k) |> FrequentItems.update_many(queries)
  top_1 = s |> FrequentItems.top_k() |> hd()
  IO.puts("k=#{k} (#{FrequentItems.size_bytes(s)} bytes): top term error bound=#{top_1.error}")
end

Merging

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

worker_a = FrequentItems.new(k: 20) |> FrequentItems.update_many(first_half)
worker_b = FrequentItems.new(k: 20) |> FrequentItems.update_many(second_half)

merged = FrequentItems.merge(worker_a, worker_b)
merged |> FrequentItems.top_k() |> Enum.take(3)

Serialization

binary = FrequentItems.serialize(sketch)
{:ok, restored} = FrequentItems.deserialize(binary)
IO.puts("Round-tripped top term: #{restored |> FrequentItems.top_k() |> hd() |> Map.get(:item)}")