# ULL (UltraLogLog) Tutorial

```elixir
Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])
```

## Introduction

`ExDataSketch.ULL` (UltraLogLog, Ertl 2023) solves the same problem as
HLL the same basic way -- hash each event, track the longest
leading-zero run per bucket -- but squeezes more signal out of each
byte. Where HLL keeps one plain rank per register, ULL packs a
geometric rank *and* a 2-bit sub-bucket refinement into the same byte,
and combines all `2^p` registers with the `OptimalFGRAEstimator`
instead of a harmonic mean. Same register count, same byte-per-register
footprint, more accurate estimate:

```mermaid
flowchart LR
    A[event] --> B["hash(event)"]
    B --> C["first p bits\n= register index"]
    B --> D["remaining bits\n= geometric rank +\n2-bit sub-bucket"]
    C --> E["registers[index] =\nmax(current, packed byte)"]
    D --> E
    E --> F["OptimalFGRAEstimator\nacross 2^p registers"]
    F --> G["cardinality\nestimate"]
```

**Use it for:** exactly what you'd use HLL for -- distinct-count
questions at fixed memory -- when you're starting fresh with no
existing HLL data to stay compatible with. It's a drop-in: same `new/1`,
`update/2`, `merge/2`, `size_bytes/1` API as `ExDataSketch.HLL`.

**Don't use it for:** anywhere you need Apache DataSketches HLL
interop, or you're reading/writing sketches an existing HLL-based
system already produced -- use `ExDataSketch.HLL` there instead (see
`guides/apache_interop.md`). Same non-uses as HLL otherwise: not for
exact counts, membership testing, or per-item frequency.

**What it buys you:** at equal memory, lower error. The measured
relative standard error is `~0.70/sqrt(m)` for ULL versus `~1.04/sqrt(m)`
for HLL (`m = 2^p` registers) -- about 30% tighter, for the same byte
count:

| Approach                  | Memory (p=14) | Error (RSE) |
| -------------------------- | -------------- | ------------ |
| `ExDataSketch.HLL` (p=14) | 16 KB          | ~0.81%       |
| `ExDataSketch.ULL` (p=14) | 16 KB          | ~0.55%       |

If you have no HLL-compatibility constraint, ULL is usually the better
default for a new distinct-count problem.

## Sample data (cached locally)

2,000,000 session events from 300,000 distinct sessions.

```elixir
events = ExDataSketch.SampleData.ull_events()
IO.puts("#{length(events)} events ready (true distinct count: 300,000)")
```

## Basic usage

The API mirrors `ExDataSketch.HLL` exactly -- `new/1`, `update/2`,
`update_many/2`, `estimate/1`, `merge/2`, `merge_many/1`, `serialize/1`,
`deserialize/1`, `from_enumerable/2` -- so switching between them is a
one-line change:

```elixir
alias ExDataSketch.ULL

sketch = ULL.from_enumerable(events, p: 14)

estimate = ULL.estimate(sketch)
true_count = 300_000
error_pct = abs(estimate - true_count) / true_count * 100

IO.puts("Estimate: #{Float.round(estimate, 0)}")
IO.puts("Error: #{Float.round(error_pct, 3)}%")
IO.puts("Sketch size: #{ULL.size_bytes(sketch)} bytes")
```

## ULL vs HLL: accuracy at equal memory

Same precision, same input, same byte count -- compare the estimates:

```elixir
alias ExDataSketch.HLL

for p <- [10, 12, 14, 16] do
  ull = ULL.from_enumerable(events, p: p)
  hll = HLL.from_enumerable(events, p: p)

  ull_error = abs(ULL.estimate(ull) - 300_000) / 300_000 * 100
  hll_error = abs(HLL.estimate(hll) - 300_000) / 300_000 * 100

  IO.puts(
    "p=#{p} (#{ULL.size_bytes(ull)} bytes): " <>
      "ULL error=#{Float.round(ull_error, 3)}%, HLL error=#{Float.round(hll_error, 3)}%"
  )
end
```

Run this a few times (re-evaluate the cell) -- any single run is noisy,
but ULL's error should be lower than HLL's on average across runs, per
the ~30% measured improvement. See `ExDataSketch.ULL`'s moduledoc for why
(a compressed per-register encoding with an extra sub-bucket refinement,
and the OptimalFGRAEstimator instead of HLL's harmonic mean).

### Why 4..26, and why it's a *hard* limit here

Both families share `p >= 4` as a real algorithmic floor (see
`hll.livemd`'s "Why 4..26?" for the reason -- it applies to ULL too).
The ceiling is where they differ: `ExDataSketch.HLL`'s `p <= 26` is just
a practical choice with no algorithmic basis, but ULL's `p <= 26` is a
**hard limit** -- Ertl (2023)'s `ESTIMATION_FACTORS` lookup table has
exactly 24 published entries, indexed by `p - 3`, giving a valid range
of `p in 3..26`. This library additionally requires `p >= 4` (one higher
than the table's own floor) purely to match HLL's floor, not because
`p = 3` is actually unsafe for ULL. Raising ULL's ceiling past 26 would
need the paper's authors (or an independent from-scratch derivation) to
publish more table entries -- unlike HLL's ceiling, it can't be done by
just changing a constant.

## Merging

Same associative/commutative merge as HLL:

```elixir
half = div(length(events), 2)
{first_half, second_half} = Enum.split(events, half)

worker_a = ULL.from_enumerable(first_half, p: 14)
worker_b = ULL.from_enumerable(second_half, p: 14)

merged = ULL.merge(worker_a, worker_b)
IO.puts("Merged estimate: #{Float.round(ULL.estimate(merged), 0)} (true: 300,000)")
```

## Serialization

```elixir
sketch = ULL.from_enumerable(Enum.take(events, 100_000), p: 14)
binary = ULL.serialize(sketch)
{:ok, restored} = ULL.deserialize(binary)

IO.puts("Round-tripped estimate: #{Float.round(ULL.estimate(restored), 0)}")
```

## Operational guidance

`p >= 10` is recommended -- the measured error bound (`~0.70/sqrt(m)`) is
tight across the full cardinality range at this precision and above. See
`ExDataSketch.ULL`'s moduledoc "Recommended Precision" section for the
full explanation and `guides/streaming_sketches.md` for accuracy
properties backed by property-based tests.

## See also

* `ExDataSketch.ULL` module documentation -- full API reference, including
  the estimator internals (the OptimalFGRAEstimator's small-range/large-range
  correction terms and per-register contribution table).
* `ExDataSketch.HLL` -- see `livebooks/sketches/hll.livemd`.