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

KLL (Karnin-Lang-Liberty) quantiles sketch for rank and quantile estimation.

KLL maintains multiple levels of sorted float64 items to provide approximate
quantile queries with guaranteed rank accuracy. Unlike HLL, CMS, and Theta
sketches, KLL operates on raw numeric values rather than hashed items.

## Accuracy

The rank error bound is approximately `1.65 / k`, where `k` is the accuracy
parameter. For the default `k = 200`, this gives roughly 0.8% rank error.

| k   | ~Rank Error |
|-----|-------------|
| 50  | 3.30%       |
| 100 | 1.65%       |
| 200 | 0.83%       |
| 500 | 0.33%       |

This is a **rank** error bound, not a value error bound -- it caps how far
off the estimated *rank* of a query can be, not how far off the returned
*value* is. Those are the same thing almost everywhere, but they diverge
sharply at a distributional discontinuity: if the true CDF jumps steeply
over a small rank range (a dense cluster ending and a sparse region or
distinct cluster beginning right after it), a small, well-within-bound
rank error can land on a value far from the query's true value, simply
because few samples exist in that rank neighborhood to bound the value
gap. This is inherent to every rank-approximate quantile sketch (KLL,
t-digest, GK, ...), not specific to this implementation -- querying
`quantile/2` exactly at such a cliff can show much larger *value* error
than the rank-error table above would suggest, even with a correct
implementation. See `livebooks/sketches/kll.livemd`'s "Accuracy" section
for a concrete, reproducible example.

## Binary State Layout (v1)

All multi-byte fields are little-endian.

    Offset  Size                    Field
    ------  ------                  -----
    0       1                       Version (u8, currently 1)
    1       4                       k parameter (u32 little-endian)
    5       8                       n total items seen (u64 little-endian)
    13      8                       min_val (f64 little-endian, NaN = empty)
    21      8                       max_val (f64 little-endian, NaN = empty)
    29      1                       num_levels (u8)
    30      ceil(num_levels/8)      compaction parity bits (1 bit per level)
    30+P    num_levels * 4          level_sizes (u32 little-endian each)
    30+P+L  sum(level_sizes) * 8    items (f64 little-endian, level 0 first)

## Apache DataSketches Interop

`serialize_datasketches/2` and `deserialize_datasketches/2` implement
the Apache DataSketches KLL compact binary format (`KllFloatsSketch`/
`KllDoublesSketch`), enabling cross-language compatibility with Java,
C++, and Python DataSketches libraries. See
`ExDataSketch.DataSketches.KLLSketch` for the binary layout and
`guides/apache_interop.md` for the full interop story. Unlike Theta,
KLL does not hash its inputs, so this is a full item-level round trip
with no hash-equality caveat.

## Options

- `:k` - accuracy parameter, integer 8..65535 (default: 200).
  Higher values use more memory but give better accuracy.
- `:backend` - backend module (default: `ExDataSketch.Backend.Pure`).

## Merge Properties

KLL merge is **associative** and **commutative** at the estimate level.
Quantile query results from merged sketches are equivalent regardless of
merge order, though internal state may differ due to compaction parity.

# `t`

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

# `capabilities`

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

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

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

## Examples

    iex> ExDataSketch.KLL.capabilities() |> MapSet.member?(:count)
    true

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

# `cdf`

```elixir
@spec cdf(t(), [number()]) :: [float()] | nil
```

Returns the Cumulative Distribution Function (CDF) at the given split points.

Given split points `[s1, s2, ..., sm]`, returns `[rank(s1), rank(s2), ..., rank(sm)]`.
Each value is the approximate fraction of items less than or equal to the
corresponding split point.

Returns `nil` if the sketch is empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100)
    iex> cdf = ExDataSketch.KLL.cdf(sketch, [25.0, 50.0, 75.0])
    iex> length(cdf)
    3

# `count`

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

Returns the total number of items inserted into the sketch.

## Examples

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

# `deserialize`

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

Deserializes an EXSK binary into a KLL sketch.

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

## Examples

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

# `deserialize_datasketches`

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

Deserializes an Apache DataSketches KLL compact binary into a KLL sketch.

## Options

- `:variant` - `:float` or `:double` (default: `:double`). Must match
  the variant the binary was produced as -- see
  `ExDataSketch.DataSketches.KLLSketch`.

## Examples

    iex> sketch = ExDataSketch.KLL.new(k: 200) |> ExDataSketch.KLL.update_many(1..100)
    iex> binary = ExDataSketch.KLL.serialize_datasketches(sketch)
    iex> {:ok, restored} = ExDataSketch.KLL.deserialize_datasketches(binary)
    iex> ExDataSketch.KLL.count(restored)
    100

# `from_enumerable`

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

Creates a new KLL sketch from an enumerable of numeric items.

Equivalent to `new(opts) |> update_many(enumerable)`.

## Options

Same as `new/1`.

## Examples

    iex> sketch = ExDataSketch.KLL.from_enumerable([1.0, 2.0, 3.0], k: 200)
    iex> ExDataSketch.KLL.count(sketch)
    3

# `max_value`

```elixir
@spec max_value(t()) :: float() | nil
```

Returns the maximum value seen by the sketch, or `nil` if empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many([3.0, 1.0, 2.0])
    iex> ExDataSketch.KLL.max_value(sketch)
    3.0

# `merge`

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

Merges two KLL sketches.

Both sketches must have the same `k` parameter. The result is a sketch
whose quantile estimates approximate the union of both input multisets.

Returns the merged sketch. Raises `ExDataSketch.Errors.IncompatibleSketchesError`
if the sketches have different parameters.

## Examples

    iex> a = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..50)
    iex> b = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(51..100)
    iex> merged = ExDataSketch.KLL.merge(a, b)
    iex> ExDataSketch.KLL.count(merged)
    100

# `merge_many`

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

Merges a non-empty enumerable of KLL sketches into one.

Raises `Enum.EmptyError` if the enumerable is empty.

## Examples

    iex> sketches = Enum.map(1..3, fn i ->
    ...>   ExDataSketch.KLL.new() |> ExDataSketch.KLL.update(i * 1.0)
    ...> end)
    iex> merged = ExDataSketch.KLL.merge_many(sketches)
    iex> ExDataSketch.KLL.count(merged)
    3

# `merger`

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

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

The returned function calls `merge/2` on two sketches.

## Examples

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

# `min_value`

```elixir
@spec min_value(t()) :: float() | nil
```

Returns the minimum value seen by the sketch, or `nil` if empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many([3.0, 1.0, 2.0])
    iex> ExDataSketch.KLL.min_value(sketch)
    1.0

# `new`

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

Creates a new KLL sketch.

## Options

- `:k` - accuracy parameter, integer 8..65535 (default: 200).
  Higher values use more memory but give better accuracy.
- `:backend` - backend module (default: `ExDataSketch.Backend.Pure`).

## Examples

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

# `pmf`

```elixir
@spec pmf(t(), [number()]) :: [float()] | nil
```

Returns the Probability Mass Function (PMF) at the given split points.

Given split points `[s1, s2, ..., sm]`, returns `m+1` values representing
the approximate fraction of items in the intervals
`(-inf, s1], (s1, s2], ..., (sm, +inf)`.

The returned values sum to 1.0.

Returns `nil` if the sketch is empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100)
    iex> pmf = ExDataSketch.KLL.pmf(sketch, [50.0])
    iex> length(pmf)
    2

# `quantile`

```elixir
@spec quantile(t(), float()) :: float() | nil
```

Returns the approximate value at the given normalized rank.

The rank must be in the range `[0.0, 1.0]`, where 0.0 is the minimum
and 1.0 is the maximum. For example, `quantile(sketch, 0.5)` returns
the approximate median.

Returns `nil` if the sketch is empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100)
    iex> median = ExDataSketch.KLL.quantile(sketch, 0.5)
    iex> abs(median - 50.0) < 5.0
    true

# `quantiles`

```elixir
@spec quantiles(t(), [float()]) :: [float() | nil]
```

Returns approximate values at multiple normalized ranks.

Convenience wrapper around `quantile/2` for batch queries.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100)
    iex> [q25, q50, q75] = ExDataSketch.KLL.quantiles(sketch, [0.25, 0.5, 0.75])
    iex> q25 < q50 and q50 < q75
    true

# `rank`

```elixir
@spec rank(t(), number()) :: float() | nil
```

Returns the approximate normalized rank of the given value.

The result is in the range `[0.0, 1.0]`. For example, if `rank(sketch, x)`
returns 0.75, approximately 75% of the values in the sketch are <= x.

Returns `nil` if the sketch is empty.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100)
    iex> r = ExDataSketch.KLL.rank(sketch, 50.0)
    iex> abs(r - 0.5) < 0.05
    true

# `reducer`

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

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

The returned function calls `update/2` on each item.

## Examples

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

# `serialize`

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

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

The serialized binary includes magic bytes, version, sketch type,
parameters, and state. See `ExDataSketch.Codec` for format details.

## Options

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

## Examples

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

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

# `serialize_datasketches`

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

Serializes the sketch to the Apache DataSketches KLL compact binary format.

Enables cross-language interoperability with Java, C++, and Python
DataSketches libraries. See `ExDataSketch.DataSketches.KLLSketch` for
the binary layout.

## Options

- `:variant` - `:float` or `:double` (default: `:double`). Apache's
  wire format doesn't self-describe item width, so the variant must be
  chosen explicitly -- see `ExDataSketch.DataSketches.KLLSketch`.

## Examples

    iex> sketch = ExDataSketch.KLL.new(k: 200) |> ExDataSketch.KLL.update_many(1..100)
    iex> binary = ExDataSketch.KLL.serialize_datasketches(sketch)
    iex> {:ok, restored} = ExDataSketch.KLL.deserialize_datasketches(binary)
    iex> ExDataSketch.KLL.quantile(restored, 0.5) == ExDataSketch.KLL.quantile(sketch, 0.5)
    true

# `size_bytes`

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

Returns the size of the sketch state in bytes.

## Examples

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

# `update`

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

Updates the sketch with a single numeric value.

The value is converted to float64. Unlike HLL/CMS/Theta, KLL does not
hash the input -- it stores the actual numeric value for quantile estimation.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update(42.0)
    iex> ExDataSketch.KLL.count(sketch)
    1

# `update_many`

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

Updates the sketch with multiple numeric values in a single pass.

More efficient than calling `update/2` repeatedly because it minimizes
intermediate binary allocations.

## Examples

    iex> sketch = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many([1.0, 2.0, 3.0])
    iex> ExDataSketch.KLL.count(sketch)
    3

---

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