# FrequentItems Tutorial

```elixir
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:

```mermaid
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.

```elixir
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

```elixir
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]`:

```elixir
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

```elixir
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:

```elixir
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

```elixir
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

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

## See also

* `ExDataSketch.FrequentItems` module documentation -- full API reference,
  including the SpaceSaving eviction/tie-breaking rules.
* `ExDataSketch.MisraGries` -- a different (deterministic, no
  probabilistic error bound on *which* items are tracked) heavy-hitter
  algorithm with a fraction-based `frequent/2`; see
  `livebooks/sketches/misra_gries.livemd` for how the two compare.
* `ExDataSketch.CMS` -- point-query frequency estimation instead of
  top-K; see `livebooks/sketches/cms.livemd`.