# `ExDataSketch.MisraGries`
[🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/misra_gries.ex#L1)

MisraGries sketch for deterministic heavy hitter detection.

The Misra-Gries algorithm maintains at most `k` counters to track frequent
items in a data stream. It provides a deterministic guarantee: any item
whose true frequency exceeds `n/(k+1)` (where `n` is the total count) is
guaranteed to be tracked.

## Algorithm

- **Update(x)**: If x is tracked, increment its counter. If there are fewer
  than k entries, insert x with count 1. Otherwise, decrement all counters
  by 1 and remove any that reach zero.

- **Guarantee**: If an item appears more than `n/(k+1)` times, it will be in
  the counter set when queried. The estimated count is a lower bound on the
  true count, with error at most `n/(k+1)`.

## Comparison with FrequentItems (SpaceSaving)

| Feature | MisraGries | FrequentItems |
|---------|-----------|---------------|
| Algorithm | Decrement-all | SpaceSaving (min-replacement) |
| Guarantee | Deterministic: freq > n/(k+1) always tracked | Probabilistic with error bounds |
| Counter count | At most k | Exactly k |
| Estimate | Lower bound | Estimate with overcount error |

**In practice, the two do not "just broadly agree" beyond the guaranteed
item(s).** Decrement-all discards *every* counter on a miss, including
ones for items that are genuinely frequent but fall below the `n/(k+1)`
guarantee threshold; against a workload with many moderately-frequent
items and a `k` too small to cover them, those items get evicted by
churn just as readily as truly rare ones. SpaceSaving only ever evicts
the single *minimum* counter, so items that are frequent-but-unguaranteed
tend to survive and entrench themselves in practice, even without a
guarantee covering them. Measured example: 1,000,000 power-law-distributed
events, 5,000 distinct items, `k = 20` (`n/(k+1) ~ 47,619`, cleared only by
the single most frequent item) -- `MisraGries.top_k(sketch, 3)` returned
`["query_1", "query_1144", "query_1209"]` (the latter two essentially
arbitrary low-count survivors), while `FrequentItems.top_k/1` on the same
data returned `["query_1", "query_9", "query_8"]`, much closer to the true
ranking. See "Choosing k" below for how to size `k` so this doesn't happen.

## Choosing k

- **Guarantee-driven sizing**: pick `k` so `n/(k+1)` sits comfortably below
  the smallest true frequency you need reliably retained. For a top-N
  query, that means every one of the true top N items must individually
  clear `n/(k+1)` -- there is no guarantee for items below it, and with a
  "thick middle" of many moderately-frequent items and a `k` too small to
  cover them, they are routinely evicted in practice (see above). In one
  measured example (same data as above), `k = 100` reliably recovered the
  true top 3 but not top 4-5; `k = 200` (`n/(k+1) ~ 4,975`) recovered the
  exact true top 5.
- **Memory cost of `k` is small and predictable**: state size scales with
  the number of *retained* entries (bounded by `k`), at roughly 21-22
  bytes/entry for typical string keys (`4-byte key_len + key bytes +
  8-byte count`, see "Binary State Layout" below). `k = 200` costs on the
  order of a few KB; even `k = 5000` (tracking every distinct item in a
  5,000-item universe) was ~109 KB in the same measurement.
- **CPU cost of `k` is real but far gentler than the `O(k)`-per-miss
  "decrement all" step suggests in isolation.** As `k` grows, a larger
  share of incoming items are already tracked (cheap O(1) increment)
  instead of triggering a full decrement-all, so the two effects partly
  offset. Measured example: increasing `k` 250x (20 -> 5000) increased
  `update_many/2` wall time only ~4x for the workload above -- but this
  ratio is workload-dependent; a stream whose cardinality vastly exceeds
  `k` (so most items are permanent misses) will scale closer to the naive
  `O(n*k)` case.
- **No NIF acceleration is available for this family.** Unlike most other
  `ExDataSketch` sketches, `ExDataSketch.Backend.Rust`'s `mg_*` functions
  are a thin pass-through to `ExDataSketch.Backend.Pure` -- there is no
  compiled fast path to fall back on, so `k` (and workload shape) are the
  only real levers over `update_many/2` cost for this family.

## Binary State Layout (MG01)

All multi-byte fields are little-endian.

    HEADER (22 bytes):
      magic:       4 bytes  "MG01"
      version:     u8       1
      reserved:    u8       0
      k:           u32 LE   max counters
      n:           u64 LE   total count
      entry_count: u32 LE   number of entries

    ENTRIES (variable):
      entry_count x:
        key_len:   u32 LE
        key:       key_len bytes
        count:     u64 LE

## Options

- `:k` - maximum number of counters (default: 10, must be >= 1).
- `:key_encoding` - key encoding policy: `:binary` (default), `:int`,
  or `{:term, :external}`.
- `:backend` - backend module (default: `ExDataSketch.Backend.Pure`).

## Merge Properties

MisraGries merge is **commutative**. Both sketches must have the same
`k` parameter. Count (`n`) is always exactly additive.

# `t`

```elixir
@type t() :: %ExDataSketch.MisraGries{
  backend: module(),
  opts: keyword(),
  state: binary()
}
```

# `capabilities`

```elixir
@spec capabilities() :: ExDataSketch.Sketch.capabilities()
```

Returns the set of operation names supported by `ExDataSketch.MisraGries`.

See `ExDataSketch.Sketch` for the shared capability vocabulary.

## Examples

    iex> ExDataSketch.MisraGries.capabilities() |> MapSet.member?(:estimate)
    true

    iex> ExDataSketch.MisraGries.capabilities() |> MapSet.member?(:no_such_operation)
    false

# `count`

```elixir
@spec count(t()) :: non_neg_integer()
```

Returns the total number of items inserted into the sketch.

## Examples

    iex> ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.count()
    0

# `deserialize`

```elixir
@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}
```

Deserializes an EXSK binary into a MisraGries sketch.

Returns `{:ok, sketch}` on success or `{:error, reason}` on failure.

## Examples

    iex> ExDataSketch.MisraGries.deserialize(<<"invalid">>)
    {:error, %ExDataSketch.Errors.DeserializationError{message: "deserialization failed: invalid magic bytes, expected EXSK"}}

# `entry_count`

```elixir
@spec entry_count(t()) :: non_neg_integer()
```

Returns the number of distinct tracked entries.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b", "c"])
    iex> ExDataSketch.MisraGries.entry_count(sketch)
    3

# `estimate`

```elixir
@spec estimate(t(), term()) :: non_neg_integer()
```

Returns the estimated frequency of an item.

The estimate is a lower bound on the true count. If the item is not
tracked, returns 0.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "a", "b"])
    iex> ExDataSketch.MisraGries.estimate(sketch, "a")
    2

# `frequent`

```elixir
@spec frequent(t(), float()) :: [{term(), non_neg_integer()}]
```

Returns entries whose estimated frequency exceeds the given threshold.

The threshold is a fraction in (0.0, 1.0). Returns entries whose count
is greater than `threshold * count(sketch)`.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new(k: 5)
    iex> sketch = Enum.reduce(1..100, sketch, fn _, s -> ExDataSketch.MisraGries.update(s, "heavy") end)
    iex> sketch = Enum.reduce(1..10, sketch, fn i, s -> ExDataSketch.MisraGries.update(s, "light_#{i}") end)
    iex> frequent = ExDataSketch.MisraGries.frequent(sketch, 0.5)
    iex> Enum.any?(frequent, fn {item, _count} -> item == "heavy" end)
    true

# `from_enumerable`

```elixir
@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: t()
```

Creates a new MisraGries sketch from an enumerable.

## Examples

    iex> sketch = ExDataSketch.MisraGries.from_enumerable(["a", "b", "a"], k: 5)
    iex> ExDataSketch.MisraGries.count(sketch)
    3

# `merge`

```elixir
@spec merge(t(), t()) :: t()
```

Merges two MisraGries instances.

Both sketches must have the same `k` parameter.

## Examples

    iex> a = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "a"])
    iex> b = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b"])
    iex> merged = ExDataSketch.MisraGries.merge(a, b)
    iex> ExDataSketch.MisraGries.count(merged)
    4

# `merge_many`

```elixir
@spec merge_many(Enumerable.t()) :: t()
```

Merges a non-empty enumerable of MisraGries instances into one.

## Examples

    iex> sketches = Enum.map(1..3, fn _ ->
    ...>   ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update("x")
    ...> end)
    iex> merged = ExDataSketch.MisraGries.merge_many(sketches)
    iex> ExDataSketch.MisraGries.count(merged)
    3

# `merger`

```elixir
@spec merger(keyword()) :: (t(), t() -&gt; t())
```

Returns a 2-arity merge function suitable for combining sketches.

## Examples

    iex> is_function(ExDataSketch.MisraGries.merger(), 2)
    true

# `new`

```elixir
@spec new(keyword()) :: t()
```

Creates a new MisraGries sketch.

## Options

- `:k` - maximum number of counters (default: 10, must be >= 1).
- `:key_encoding` - `:binary` (default), `:int`, or `{:term, :external}`.
- `:backend` - backend module (default: `ExDataSketch.Backend.Pure`).

## Examples

    iex> sketch = ExDataSketch.MisraGries.new(k: 10)
    iex> sketch.opts[:k]
    10
    iex> ExDataSketch.MisraGries.count(sketch)
    0

# `reducer`

```elixir
@spec reducer() :: (term(), t() -&gt; t())
```

Returns a 2-arity reducer function suitable for `Enum.reduce/3`.

## Examples

    iex> is_function(ExDataSketch.MisraGries.reducer(), 2)
    true

# `serialize`

```elixir
@spec serialize(
  t(),
  keyword()
) :: binary()
```

Serializes the sketch to the ExDataSketch-native EXSK binary format.

## Options

- `:format` - serialization format: `:v2` (default, EXSK v2 with CRC32C)
  or `:v1` (legacy EXSK v1, compatible with v0.7.x readers). MisraGries
  does not have a hash-strategy option, so v1 has no restriction.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new()
    iex> binary = ExDataSketch.MisraGries.serialize(sketch)
    iex> <<"EXSK", _rest::binary>> = binary
    iex> byte_size(binary) > 0
    true

    iex> sketch = ExDataSketch.MisraGries.new()
    iex> binary = ExDataSketch.MisraGries.serialize(sketch, format: :v1)
    iex> <<"EXSK", 1, 14, _rest::binary>> = binary

# `size_bytes`

```elixir
@spec size_bytes(t()) :: non_neg_integer()
```

Returns the size of the sketch state in bytes.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new()
    iex> ExDataSketch.MisraGries.size_bytes(sketch) > 0
    true

# `top_k`

```elixir
@spec top_k(t(), non_neg_integer()) :: [{term(), non_neg_integer()}]
```

Returns the top entries sorted by count descending.

Each entry is a `{item, count}` tuple where the item is decoded using
the configured key encoding.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new()
    iex> sketch = ExDataSketch.MisraGries.update_many(sketch, ["a", "a", "a", "b", "b", "c"])
    iex> [{top_item, top_count} | _] = ExDataSketch.MisraGries.top_k(sketch, 2)
    iex> top_item
    "a"
    iex> top_count
    3

# `update`

```elixir
@spec update(t(), term()) :: t()
```

Updates the sketch with a single item.

The item is encoded using the configured key encoding before insertion.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update("hello")
    iex> ExDataSketch.MisraGries.count(sketch)
    1

# `update_many`

```elixir
@spec update_many(t(), Enumerable.t()) :: t()
```

Updates the sketch with multiple items in a single pass.

## Examples

    iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b", "a"])
    iex> ExDataSketch.MisraGries.count(sketch)
    3

---

*Consult [api-reference.md](api-reference.md) for complete listing*