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

Production-grade streaming data sketching algorithms for Elixir.

ExDataSketch provides probabilistic data structures for approximate counting
and frequency estimation on streaming data. All sketch state is stored as
Elixir-owned binaries, enabling straightforward serialization, distribution,
and persistence.

## Sketch Families

- `ExDataSketch.HLL` -- HyperLogLog for cardinality (distinct count) estimation.
- `ExDataSketch.CMS` -- Count-Min Sketch for frequency estimation.
- `ExDataSketch.Theta` -- Theta Sketch for set operations on cardinalities.
- `ExDataSketch.KLL` -- KLL Sketch for rank and quantile estimation.
- `ExDataSketch.DDSketch` -- DDSketch for value-relative-accuracy quantile estimation.
- `ExDataSketch.FrequentItems` -- SpaceSaving for approximate heavy-hitter detection.
- `ExDataSketch.Bloom` -- Bloom filter for probabilistic membership testing.
- `ExDataSketch.Cuckoo` -- Cuckoo filter for membership testing with deletion support.
- `ExDataSketch.Quotient` -- Quotient filter for membership testing with deletion and merge.
- `ExDataSketch.CQF` -- Counting Quotient Filter for multiset membership with approximate counting.
- `ExDataSketch.XorFilter` -- Xor filter for static, immutable membership testing.
- `ExDataSketch.IBLT` -- Invertible Bloom Lookup Table for set reconciliation.
- `ExDataSketch.FilterChain` -- Capability-aware composition framework for membership filters.
- `ExDataSketch.REQ` -- REQ Sketch for relative error quantiles with tail accuracy.
- `ExDataSketch.MisraGries` -- Misra-Gries for deterministic heavy hitter detection.
- `ExDataSketch.Quantiles` -- Facade for quantile sketch algorithms.

## Unified Facade

`sketches/0` is the registry mapping each family atom (`:hll`, `:bloom`,
and so on) to its module -- the single source of truth other generic code
(`ExDataSketch.Sketch.implemented?/1`, the capability-matrix test) is
checked against. `new/2`, `update/2`, `merge/2`, `merge_many/1`,
`estimate/1`, `serialize/1`, `deserialize/2`, `size_bytes/1`, and
`capabilities/1` are generic dispatch functions that work across all 16
concrete families without the caller needing to know which module a
struct belongs to. They are additive: every per-family module
(`HLL.new/1`, `Bloom.put/2`, and so on) remains the documented, primary
API and is unaffected. See `baoulo/plans/plan-0.10.0.md` (Phase 1) and
`baoulo/plans/0.10.0_phase1_stub_review.md` for the design rationale,
including the small set of documented exceptions (`ExDataSketch.XorFilter`
has no incremental `update/2`; `ExDataSketch.Cuckoo`, `XorFilter`, and
`ExDataSketch.FilterChain` have no `merge/2`; `CMS` and the filter
families have no single-value `estimate/1`).

## Architecture

- **Binary state**: All sketch state is canonical Elixir binaries. No opaque
  NIF resources.
- **Backend system**: Computation is dispatched through backend modules.
  `ExDataSketch.Backend.Pure` (pure Elixir) is always available.
  `ExDataSketch.Backend.Rust` (optional, precompiled binaries provided) provides NIF acceleration.
- **Serialization**: ExDataSketch-native format (EXSK) for all sketches,
  plus Apache DataSketches interop for Theta CompactSketch.
- **Deterministic hashing**: `ExDataSketch.Hash` provides a stable 64-bit
  hash interface for reproducible results.

## Quick Example

    # Cardinality estimation with HLL
    sketch = ExDataSketch.HLL.new(p: 14)
    sketch = ExDataSketch.update_many(sketch, ["alice", "bob", "alice"])
    ExDataSketch.HLL.estimate(sketch)

    # Frequency estimation with CMS
    sketch = ExDataSketch.CMS.new(width: 2048, depth: 5)
    sketch = ExDataSketch.update_many(sketch, ["page_a", "page_a", "page_b"])
    ExDataSketch.CMS.estimate(sketch, "page_a")

## Integration Patterns

Each sketch module provides convenience functions for ecosystem integration:

- `from_enumerable/2` — build a sketch from any `Enumerable` in one call.
- `merge_many/1` — merge a collection of sketches (e.g. from parallel workers).
- `reducer/1` — returns a 2-arity function for use with `Enum.reduce/3`, Flow, etc.
- `merger/1` — returns a 2-arity function for merging sketches in reduce operations.

## Stream Integration

`ExDataSketch.Stream` provides terminal stream consumers that build sketches
from lazy enumerables without buffering the entire input:

    1..100_000
    |> Stream.map(&to_string/1)
    |> ExDataSketch.Stream.hll(p: 14)
    |> ExDataSketch.HLL.estimate()

For partition-local reduction:

    1..1_000_000
    |> ExDataSketch.Stream.reduce_partitioned(ExDataSketch.HLL, partitions: 8, p: 14)

## Collectable

All mergeable sketches implement the `Collectable` protocol, enabling
`Enum.into/2` usage:

    sketch = Enum.into(1..1000, ExDataSketch.HLL.new(p: 14))

See the [Integration Guide](integrations.md) for examples with Flow, Broadway,
Explorer, Nx, and other ecosystem libraries.

See the [Quick Start guide](quick_start.md) for more examples.

# `sketch_type`

```elixir
@type sketch_type() ::
  :hll
  | :ull
  | :cms
  | :theta
  | :kll
  | :ddsketch
  | :req
  | :frequent_items
  | :misra_gries
  | :bloom
  | :cuckoo
  | :quotient
  | :cqf
  | :xor_filter
  | :iblt
  | :filter_chain
```

A registry key identifying one of the 16 concrete sketch families. See
`sketches/0` for the full atom-to-module mapping.

# `capabilities`

```elixir
@spec capabilities(sketch_type() | ExDataSketch.Sketch.sketch()) ::
  ExDataSketch.Sketch.capabilities()
```

Returns the set of operation names supported by a sketch family, accepting
either a family atom (looked up via `sketches/0`) or a sketch struct
(dispatching on `sketch.__struct__`).

Raises `ExDataSketch.Errors.InvalidOptionError` if given an atom that is
not a key in `sketches/0`.

## Examples

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

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

# `deserialize`

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

Deserializes a binary produced by `serialize/1` back into a sketch of the
given family.

Takes an explicit `type` (unlike each family module's own `deserialize/1`)
because the facade cannot assume which module should own the returned
struct purely from the binary; each family module's own `deserialize/1`
independently validates the binary's embedded sketch-family marker, so
passing the wrong `type` for a binary returns `{:error, %ExDataSketch.Errors.DeserializationError{}}`
rather than silently misinterpreting the bytes.

Raises `ExDataSketch.Errors.InvalidOptionError` if `type` is not a key in
`sketches/0`.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10)
    iex> binary = ExDataSketch.serialize(sketch)
    iex> {:ok, restored} = ExDataSketch.deserialize(binary, :hll)
    iex> restored.opts[:p]
    10

    iex> {:error, error} = ExDataSketch.deserialize(<<0, 1, 2>>, :hll)
    iex> error.__struct__
    ExDataSketch.Errors.DeserializationError

# `estimate`

```elixir
@spec estimate(ExDataSketch.Sketch.sketch()) :: number()
```

Returns the sketch's headline scalar estimate, dispatching on the sketch's
struct type.

Cardinality families (`HLL`, `ULL`, `Theta`) answer with `estimate/1`.
Quantile families (`KLL`, `DDSketch`, `REQ`) and the two heavy-hitter
families (`FrequentItems`, `MisraGries`) answer with `count/1` (the total
number of ingested values). `CMS` and all membership filters have no
single-value cardinality reading -- `CMS.estimate/2` and
`FrequentItems.estimate/2` / `MisraGries.estimate/2` are per-item
questions, and a filter's own `count/1` (where present) measures something
else entirely (for example, `Bloom.count/1` is a bitset popcount, not a
cardinality estimate). Calling `estimate/1` on any of these raises
`ExDataSketch.Errors.UnsupportedOperationError` directing callers to the
family module.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("a")
    iex> ExDataSketch.estimate(sketch) > 0.0
    true

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update(1.0)
    iex> ExDataSketch.estimate(sketch)
    1

    iex> try do
    ...>   ExDataSketch.estimate(ExDataSketch.CMS.new())
    ...> rescue
    ...>   e in ExDataSketch.Errors.UnsupportedOperationError -> e.message
    ...> end
    "ExDataSketch.CMS (no single-value cardinality estimate; call the family module directly) does not support estimate/1"

# `merge`

```elixir
@spec merge(ExDataSketch.Sketch.sketch(), ExDataSketch.Sketch.sketch()) ::
  ExDataSketch.Sketch.sketch() | {:error, Exception.t()}
```

Merges two sketches of the same family and compatible parameters,
dispatching on the sketches' struct type.

Three families have no associative merge and raise
`ExDataSketch.Errors.UnsupportedOperationError`: `ExDataSketch.Cuckoo`
(bucket state is not associatively mergeable), `ExDataSketch.XorFilter`
(immutable once built), and `ExDataSketch.FilterChain` (chains have no
merge semantics). Merging two sketches of different families returns
`{:error, %ExDataSketch.Errors.IncompatibleSketchesError{}}`. Merging two
sketches of the same family with incompatible parameters (for example, two
HLLs with different `p`) raises `ExDataSketch.Errors.IncompatibleSketchesError`,
same as calling the family module's own `merge/2` directly.

## Examples

    iex> a = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("a")
    iex> b = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("b")
    iex> merged = ExDataSketch.merge(a, b)
    iex> ExDataSketch.HLL.estimate(merged) > 0.0
    true

    iex> {:error, error} = ExDataSketch.merge(ExDataSketch.HLL.new(p: 10), ExDataSketch.CMS.new())
    iex> error.__struct__
    ExDataSketch.Errors.IncompatibleSketchesError

# `merge_many`

```elixir
@spec merge_many([ExDataSketch.Sketch.sketch(), ...]) :: ExDataSketch.Sketch.sketch()
```

Merges a non-empty list of sketches of the same family, dispatching on the
sketches' struct type via `merge/2`.

## Examples

    iex> sketches = [
    ...>   ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("a"),
    ...>   ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("b"),
    ...>   ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("c")
    ...> ]
    iex> merged = ExDataSketch.merge_many(sketches)
    iex> ExDataSketch.HLL.estimate(merged) > 0.0
    true

# `new`

```elixir
@spec new(
  sketch_type(),
  keyword()
) :: ExDataSketch.Sketch.sketch()
```

Creates a new sketch of the given family.

Dispatches to `module.new(opts)` for the module registered under `type` in
`sketches/0`.

Two families do not follow the common `new/1` shape and are special-cased:

  - `:filter_chain` -- `ExDataSketch.FilterChain.new/0` takes no options.
    Passing a non-empty `opts` raises `ExDataSketch.Errors.InvalidOptionError`.
  - `:xor_filter` -- `ExDataSketch.XorFilter` has no incremental constructor;
    it is built once from a complete item set via
    `ExDataSketch.XorFilter.build/2`. Calling `new/2` with `:xor_filter`
    raises `ExDataSketch.Errors.UnsupportedOperationError` directing
    callers to `build/2`.

Raises `ExDataSketch.Errors.InvalidOptionError` if `type` is not a key in
`sketches/0`.

## Examples

    iex> sketch = ExDataSketch.new(:hll, p: 10)
    iex> match?(%ExDataSketch.HLL{}, sketch)
    true

    iex> chain = ExDataSketch.new(:filter_chain)
    iex> ExDataSketch.FilterChain.stages(chain)
    []

    iex> try do
    ...>   ExDataSketch.new(:xor_filter)
    ...> rescue
    ...>   e in ExDataSketch.Errors.UnsupportedOperationError -> e.message
    ...> end
    "ExDataSketch.XorFilter (build-once; use ExDataSketch.XorFilter.build/2 with the full item set) does not support new/2"

    iex> try do
    ...>   ExDataSketch.new(:no_such_family)
    ...> rescue
    ...>   e in ExDataSketch.Errors.InvalidOptionError -> e.option
    ...> end
    :type

# `serialize`

```elixir
@spec serialize(ExDataSketch.Sketch.sketch()) :: binary()
```

Serializes a sketch to its canonical binary representation, dispatching on
the sketch's struct type.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10)
    iex> is_binary(ExDataSketch.serialize(sketch))
    true

# `size_bytes`

```elixir
@spec size_bytes(ExDataSketch.Sketch.sketch()) :: non_neg_integer()
```

Returns the size, in bytes, of a sketch's serialized state, dispatching on
the sketch's struct type.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10)
    iex> ExDataSketch.size_bytes(sketch) > 0
    true

# `sketches`

```elixir
@spec sketches() :: %{required(sketch_type()) =&gt; module()}
```

Returns the registry mapping every sketch family's atom key to its module.

This is the single source of truth for which atom names which concrete
sketch module. `update_many/2` below and `ExDataSketch.Sketch.implemented?/1`
are checked against this map (see the capability-matrix test in
`test/ex_data_sketch_sketch_test.exs`), so they cannot drift from it.
`ExDataSketch.Stream`'s per-family functions and `ExDataSketch.Collectable`'s
`defimpl` blocks still enumerate families independently and are not yet
reconciled against this registry.

## Examples

    iex> ExDataSketch.sketches()[:hll]
    ExDataSketch.HLL

    iex> map_size(ExDataSketch.sketches())
    16

    iex> Enum.all?(ExDataSketch.sketches(), fn {_type, module} -> Code.ensure_loaded?(module) end)
    true

# `update`

```elixir
@spec update(ExDataSketch.Sketch.sketch(), term()) :: ExDataSketch.Sketch.sketch()
```

Updates a sketch with a single item, dispatching on the sketch's struct
type.

`ExDataSketch.XorFilter` has no incremental update (it is immutable once
built) and raises `ExDataSketch.Errors.UnsupportedOperationError` directing
callers to `ExDataSketch.XorFilter.build/2`.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10)
    iex> sketch = ExDataSketch.update(sketch, "a")
    iex> ExDataSketch.HLL.estimate(sketch) > 0.0
    true

    iex> try do
    ...>   {:ok, filter} = ExDataSketch.XorFilter.build(["a"])
    ...>   ExDataSketch.update(filter, "b")
    ...> rescue
    ...>   e in ExDataSketch.Errors.UnsupportedOperationError -> e.message
    ...> end
    "ExDataSketch.XorFilter (immutable once built; see ExDataSketch.XorFilter.build/2) does not support update/2"

# `update_many`

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

Updates a sketch with multiple items in a single pass, dispatching on the
sketch's struct type.

Works for all 16 concrete families except `ExDataSketch.XorFilter`, which
has no incremental update (it is immutable once built) and raises
`ExDataSketch.Errors.UnsupportedOperationError` directing callers to
`ExDataSketch.XorFilter.build/2`.

Before this release, this function was a hand-written list of 13 struct
clauses covering the families that predated the `ExDataSketch.Sketch`
behaviour's `update_many/2` callback. Every mergeable family now
implements `update_many/2` directly (delegating to `put_many/2` where that
remains the family-idiomatic name), so this function dispatches generically
instead of re-enumerating the family list -- one of the three
independently-drifting lists named in `sketches/0`'s documentation.

## Examples

    iex> sketch = ExDataSketch.HLL.new(p: 10)
    iex> sketch = ExDataSketch.update_many(sketch, ["a", "b"])
    iex> ExDataSketch.HLL.estimate(sketch) > 0.0
    true

    iex> chain = ExDataSketch.FilterChain.new() |> ExDataSketch.FilterChain.add_stage(ExDataSketch.Bloom.new(capacity: 100))
    iex> chain = ExDataSketch.update_many(chain, ["a", "b", "c"])
    iex> ExDataSketch.FilterChain.member?(chain, "a")
    true

---

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