ULL (UltraLogLog) Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"},
])

Introduction

ExDataSketch.ULL is a newer (Ertl, 2023) alternative to HLL for the exact same job -- distinct-count estimation -- with about 30% better accuracy at the same memory footprint (same 2^p register array, one byte per register either way). If you're choosing a cardinality estimator today with no existing HLL data to stay compatible with, ULL is usually the better default; use HLL specifically when you need Apache DataSketches interop or you're reading/writing sketches an existing HLL-based system already produced.

Sample data (cached locally)

cache_path = Path.join(System.tmp_dir!(), "ex_data_sketch_livebook_cache/ull_sample.bin")

events =
  if File.exists?(cache_path) do
    IO.puts("Loading cached sample data from #{cache_path}")
    cache_path |> File.read!() |> :erlang.binary_to_term()
  else
    IO.puts("Generating sample data (this takes a few seconds)...")
    # 2,000,000 session events from 300,000 distinct sessions.
    events = for _ <- 1..2_000_000, do: "session_#{:rand.uniform(300_000)}"
    File.mkdir_p!(Path.dirname(cache_path))
    File.write!(cache_path, :erlang.term_to_binary(events))
    events
  end

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).

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.