# `ExDataSketch.ULL` [🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/ull.ex#L1) UltraLogLog (ULL) sketch for cardinality estimation. ULL (Ertl, 2023) provides approximately 20% better accuracy than HLL at the same memory footprint. It uses the same `2^p` register array as HLL, but each register byte stores a compressed 3-bit window of a per-bucket accumulator: the position of the highest bit ever recorded for that bucket (the geometric rank, via a `pack`/`unpack` encoding) plus the two bits just below it as a sub-bucket refinement. Estimation uses the OptimalFGRAEstimator from Ertl 2023: closed-form small-range and large-range correction terms plus a per-register contribution lookup table for the bulk of the range. ## Memory and Accuracy - Register count: `m = 2^p` - Memory: `8 + m` bytes (8-byte header + one byte per register) - Relative standard error: approximately `0.70 / sqrt(m)` (vs `1.04 / sqrt(m)` for HLL), measured empirically over repeated trials against this implementation | p | Registers | Memory | ~Error (ULL) | ~Error (HLL) | |----|-----------|---------|--------------|--------------| | 10 | 1,024 | ~1 KiB | 2.17% | 3.25% | | 12 | 4,096 | ~4 KiB | 1.09% | 1.63% | | 14 | 16,384 | ~16 KiB | 0.55% | 0.81% | | 16 | 65,536 | ~64 KiB | 0.27% | 0.41% | ## Estimation Strategy Every register byte is classified into one of two regimes: 1. **Small/large-range registers** (values near the encoding's boundaries): pooled into closed-form quadratic-root correction terms (`smallRangeEstimate`/`largeRangeEstimate` from Ertl 2023), analogous to HyperLogLog's linear-counting correction but generalized to this encoding's extra sub-bucket bits. 2. **Normal-range registers**: each contributes a precomputed value from a 236-entry lookup table indexed by its distance from a precision-dependent offset. The contributions are summed and combined via `estimation_factor[p] * sum^(-1/tau)` (`tau ≈ 0.819`), a single smooth formula that scales continuously from small to large cardinalities -- unlike HLL/the pre-v0.10.2 ULL implementation, there is no separate linear-counting branch or explicit large-range correction. ## Recommended Precision - `p >= 10` is recommended for production use; the measured RSE bound (`~0.70/sqrt(m)`) is tight across the full cardinality range at this precision and above. ## Precision Range (4..26) Unlike `ExDataSketch.HLL` (whose `p <= 26` is a practical ceiling with no algorithmic basis -- see its moduledoc), ULL's `p <= 26` is a **hard limit**: the `estimation_factor[p]` lookup table (`ESTIMATION_FACTORS` in the reference implementation) has exactly 24 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 for consistency with HLL's own floor, not because `p = 3` is unsafe for ULL. Raising the ceiling past 26 would require Ertl 2023's authors (or a from-scratch derivation) to publish additional table entries -- it cannot be done by simply changing a constant, unlike HLL. ## Binary State Layout (ULL1) All multi-byte fields are little-endian. Offset Size Field ------ ------ ----- 0 4 Magic bytes: "ULL1" 4 1 Version (u8, currently 2) 5 1 Precision p (u8, 4..26) 6 2 Reserved flags (u16 little-endian, must be 0) 8 m Registers (m = 2^p bytes, one u8 per register) Total: 8 + 2^p bytes. Version 2 (v0.10.2+) replaced the register encoding and estimator used in version 1, which was an HLL-derived approximation rather than the real UltraLogLog algorithm and produced significantly overestimated cardinality once every register had been touched at least once. Version-1 binaries are rejected on decode with a clear error rather than silently misinterpreted -- see `deserialize/1`. ## Options - `:p` - precision parameter, integer 4..26 (default: 14) - `:backend` - backend module (default: `ExDataSketch.Backend.Pure`) - `:update_many_chunk_size` - chunk size for `update_many/2` internal batching (default: 10000). Must be set at creation time; cannot be overridden on a per-call basis. ## Merge Properties ULL merge is **associative** and **commutative** (register-wise max). This means sketches can be merged in any order or grouping and produce the same result, making ULL safe for parallel and distributed aggregation. # `t` ```elixir @type t() :: %ExDataSketch.ULL{backend: module(), opts: keyword(), state: binary()} ``` # `capabilities` ```elixir @spec capabilities() :: ExDataSketch.Sketch.capabilities() ``` Returns the set of operation names supported by `ExDataSketch.ULL`. See `ExDataSketch.Sketch` for the shared capability vocabulary. ## Examples iex> ExDataSketch.ULL.capabilities() |> MapSet.member?(:estimate) true iex> ExDataSketch.ULL.capabilities() |> MapSet.member?(:no_such_operation) false # `count` ```elixir @spec count(t()) :: float() ``` Alias for `estimate/1`. ## Examples iex> ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.count() 0.0 # `deserialize` ```elixir @spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()} ``` Deserializes an EXSK binary into a ULL sketch. Returns `{:ok, sketch}` on success or `{:error, reason}` on failure. ## Examples iex> ExDataSketch.ULL.deserialize(<<"invalid">>) {:error, %ExDataSketch.Errors.DeserializationError{message: "deserialization failed: invalid magic bytes, expected EXSK"}} # `estimate` ```elixir @spec estimate(t()) :: float() ``` Estimates the number of distinct items in the sketch. Returns a floating-point estimate. The accuracy depends on the precision parameter `p`. ULL typically achieves ~20% lower relative error than HLL at the same precision. ## Examples iex> ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.estimate() 0.0 # `from_enumerable` ```elixir @spec from_enumerable( Enumerable.t(), keyword() ) :: t() ``` Creates a new ULL sketch from an enumerable of items. Equivalent to `new(opts) |> update_many(enumerable)`. ## Options Same as `new/1`. ## Examples iex> sketch = ExDataSketch.ULL.from_enumerable(["a", "b", "c"], p: 10) iex> ExDataSketch.ULL.estimate(sketch) > 0.0 true # `merge` ```elixir @spec merge(t(), t()) :: t() ``` Merges two ULL sketches. Both sketches must have the same precision `p`. The result contains the register-wise maximum, which corresponds to the union of the two input multisets. Returns the merged sketch. Raises `ExDataSketch.Errors.IncompatibleSketchesError` if the sketches have different parameters. ## Examples iex> a = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update("x") iex> b = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update("y") iex> merged = ExDataSketch.ULL.merge(a, b) iex> ExDataSketch.ULL.estimate(merged) >= ExDataSketch.ULL.estimate(a) true # `merge_many` ```elixir @spec merge_many(Enumerable.t()) :: t() ``` Merges a non-empty enumerable of ULL sketches into one. Raises `Enum.EmptyError` if the enumerable is empty. ## Examples iex> a = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update("x") iex> b = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update("y") iex> merged = ExDataSketch.ULL.merge_many([a, b]) iex> ExDataSketch.ULL.estimate(merged) > 0.0 true # `merger` ```elixir @spec merger(keyword()) :: (t(), t() -> 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.ULL.merger(), 2) true # `new` ```elixir @spec new(keyword()) :: t() ``` Creates a new ULL sketch. ## Options - `:p` - precision parameter, integer 4..26 (default: 14). Higher values use more memory but give better accuracy. - `:backend` - backend module (default: `ExDataSketch.Backend.Pure`). - `:hash_fn` - custom hash function `(term -> non_neg_integer)`. - `:seed` - hash seed (default: 0). ## Examples iex> sketch = ExDataSketch.ULL.new(p: 10) iex> sketch.opts[:p] 10 iex> ExDataSketch.ULL.size_bytes(sketch) 1032 # `reducer` ```elixir @spec reducer() :: (term(), t() -> 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.ULL.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). The v1 format is only valid for sketches using `:phash2` hash strategy. ## Examples iex> sketch = ExDataSketch.ULL.new(p: 10) iex> binary = ExDataSketch.ULL.serialize(sketch) iex> <<"EXSK", _rest::binary>> = binary iex> byte_size(binary) > 0 true iex> sketch = ExDataSketch.ULL.new(p: 10, hash_strategy: :phash2) iex> binary = ExDataSketch.ULL.serialize(sketch, format: :v1) iex> <<"EXSK", 1, 15, _rest::binary>> = binary # `size_bytes` ```elixir @spec size_bytes(t()) :: non_neg_integer() ``` Returns the size of the sketch state in bytes. ## Examples iex> ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.size_bytes() 1032 # `update` ```elixir @spec update(t(), term()) :: t() ``` Updates the sketch with a single item. The item is hashed using `ExDataSketch.Hash.hash64/1` before being inserted into the sketch. ## Examples iex> sketch = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update("hello") iex> ExDataSketch.ULL.estimate(sketch) > 0.0 true # `update_many` ```elixir @spec update_many(t(), Enumerable.t()) :: t() ``` Updates the sketch with multiple items in a single pass. More efficient than calling `update/2` repeatedly because it minimizes intermediate binary allocations. The internal batch size is controlled by `:update_many_chunk_size`, which must be set at `new/1` time and cannot be changed per call. ## Examples iex> sketch = ExDataSketch.ULL.new(p: 10) |> ExDataSketch.ULL.update_many(["a", "b", "c"]) iex> ExDataSketch.ULL.estimate(sketch) > 0.0 true --- *Consult [api-reference.md](api-reference.md) for complete listing*