# `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 but stores a different value per register that encodes both the geometric rank and an extra sub-bucket bit, then applies the FGRA estimator (sigma/tau convergence from Ertl 2017) instead of HLL's harmonic mean. ## Memory and Accuracy - Register count: `m = 2^p` - Memory: `8 + m` bytes (8-byte header + one byte per register) - Relative standard error: approximately `0.835 / sqrt(m)` (vs `1.04 / sqrt(m)` for HLL) | p | Registers | Memory | ~Error (ULL) | ~Error (HLL) | |----|-----------|---------|--------------|--------------| | 10 | 1,024 | ~1 KiB | 2.61% | 3.25% | | 12 | 4,096 | ~4 KiB | 1.30% | 1.63% | | 14 | 16,384 | ~16 KiB | 0.65% | 0.81% | | 16 | 65,536 | ~64 KiB | 0.33% | 0.41% | ## Binary State Layout (ULL1) All multi-byte fields are little-endian. Offset Size Field ------ ------ ----- 0 4 Magic bytes: "ULL1" 4 1 Version (u8, currently 1) 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. ## Options - `:p` - precision parameter, integer 4..26 (default: 14) - `:backend` - backend module (default: `ExDataSketch.Backend.Pure`) ## 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()} ``` # `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()) :: 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. ## 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 # `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. ## 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*