ULL (UltraLogLog) Tutorial

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:

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.

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:

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:

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:

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

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.