ExDataSketch.MisraGries (ExDataSketch v0.10.1)

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.

Summary

Types

t()

Functions

capabilities()

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

count(misra_gries)

Returns the total number of items inserted into the sketch.

deserialize(binary)

Deserializes an EXSK binary into a MisraGries sketch.

entry_count(misra_gries)

Returns the number of distinct tracked entries.

estimate(misra_gries, item)

Returns the estimated frequency of an item.

frequent(sketch, threshold)

Returns entries whose estimated frequency exceeds the given threshold.

from_enumerable(enumerable, opts \\ [])

Creates a new MisraGries sketch from an enumerable.

merge(sketch, misra_gries)

Merges two MisraGries instances.

merge_many(sketches)

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

merger(opts \\ [])

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

new(opts \\ [])

Creates a new MisraGries sketch.

reducer()

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

serialize(misra_gries, serialize_opts \\ [])

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

size_bytes(misra_gries)

Returns the size of the sketch state in bytes.

top_k(misra_gries, limit)

Returns the top entries sorted by count descending.

update(sketch, item)

Updates the sketch with a single item.

update_many(sketch, items)

Updates the sketch with multiple items in a single pass.

Types

t()

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

Functions

capabilities()

@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(misra_gries)

@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(binary)

@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(misra_gries)

@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(misra_gries, item)

@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(sketch, threshold)

@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(enumerable, opts \\ [])

@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(sketch, misra_gries)

@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(sketches)

@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(opts \\ [])

@spec merger(keyword()) :: (t(), t() -> t())

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

Examples

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

new(opts \\ [])

@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()

@spec reducer() :: (term(), t() -> t())

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

Examples

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

serialize(misra_gries, serialize_opts \\ [])

@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(misra_gries)

@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(misra_gries, limit)

@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(sketch, item)

@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(sketch, items)

@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