# `ExDataSketch.HLL` [🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/hll.ex#L1) HyperLogLog (HLL) sketch for cardinality estimation. HLL provides approximate distinct-count estimates using sublinear memory. The precision parameter `p` controls the trade-off between memory usage and accuracy: higher `p` means more memory but better estimates. ## Memory and Accuracy - Register count: `m = 2^p` - Memory: `m` bytes (one byte per register in v1 format) - Relative standard error: approximately `1.04 / sqrt(m)` | p | Registers | Memory | ~Error | |----|------------|---------|--------| | 10 | 1,024 | 1 KiB | 3.25% | | 12 | 4,096 | 4 KiB | 1.63% | | 14 | 16,384 | 16 KiB | 0.81% | | 16 | 65,536 | 64 KiB | 0.41% | | 20 | 1,048,576 | 1 MiB | 0.10% | | 26 | 67,108,864 | 64 MiB | 0.013% | ## Precision Range (4..26) - **`p >= 4` is a hard requirement.** The bias-correction constant `alpha(m)` is only defined for `m = 2^p in {16, 32, 64}` as exact published values, with a general asymptotic formula covering every `m >= 128` (i.e. every `p >= 7`); together these cover `p >= 4` exactly, with no case for `p < 4`. This is a real algorithmic floor, not a convention. - **`p <= 26` is a practical ceiling, not an algorithmic one.** Nothing in the register encoding or estimator caps `p` below 26 -- registers are a plain byte each (max representable rank is `64 - p + 1`, far under 255 for any realistic `p`), and `alpha(m)`'s general formula is valid for any `m >= 128`. 26 is chosen to match `ExDataSketch.ULL`'s ceiling (itself a hard limit -- see its moduledoc) so the two cardinality estimators offer the same maximum precision/memory budget for a like-for-like choice between them. At `p = 26` a single sketch is 64 MiB; most workloads need nowhere near this and should stay at `p <= 18` or so. ## Binary State Layout (v1) All multi-byte fields are little-endian. Offset Size Field ------ ------ ----- 0 1 Version (u8, currently 1) 1 1 Precision p (u8, 4..26) 2 2 Reserved flags (u16 little-endian, must be 0) 4 m Registers (m = 2^p bytes, one u8 per register) Total: 4 + 2^p bytes. ## Options - `:p` - precision parameter, integer 4..26 (default: 14). See "Precision Range" above. - `:backend` - backend module (default: `ExDataSketch.Backend.Pure`) ## Merge Properties HLL 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 HLL safe for parallel and distributed aggregation. # `t` ```elixir @type t() :: %ExDataSketch.HLL{backend: module(), opts: keyword(), state: binary()} ``` # `capabilities` ```elixir @spec capabilities() :: ExDataSketch.Sketch.capabilities() ``` Returns the set of operation names supported by `ExDataSketch.HLL`. See `ExDataSketch.Sketch` for the shared capability vocabulary. ## Examples iex> ExDataSketch.HLL.capabilities() |> MapSet.member?(:estimate) true iex> ExDataSketch.HLL.capabilities() |> MapSet.member?(:no_such_operation) false # `deserialize` ```elixir @spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()} ``` Deserializes an EXSK binary into an HLL sketch. Accepts both EXSK v1 (legacy, pre-v0.8.0) and EXSK v2 frames; the version is sniffed from the magic-prefixed header. v2 frames carry a CRC32C trailer that is verified before decoding; corruption is reported as a structured `DeserializationError`. Returns `{:ok, sketch}` on success or `{:error, reason}` on failure. ## Examples iex> ExDataSketch.HLL.deserialize(<<"invalid">>) {:error, %ExDataSketch.Errors.DeserializationError{message: "deserialization failed: invalid magic bytes, expected EXSK"}} # `deserialize_datasketches` ```elixir @spec deserialize_datasketches(binary()) :: {:ok, t()} | {:error, Exception.t()} ``` Deserializes an Apache DataSketches HLL binary. Not implemented. See `serialize_datasketches/1` for details. ## Examples iex> try do ...> ExDataSketch.HLL.deserialize_datasketches(<<>>) ...> rescue ...> e in ExDataSketch.Errors.NotImplementedError -> e.message ...> end "ExDataSketch.HLL.deserialize_datasketches is not yet implemented" # `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`. ## Examples iex> ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.estimate() 0.0 # `from_enumerable` ```elixir @spec from_enumerable( Enumerable.t(), keyword() ) :: t() ``` Creates a new HLL sketch from an enumerable of items. Equivalent to `new(opts) |> update_many(enumerable)`. ## Options Same as `new/1`. ## Examples iex> sketch = ExDataSketch.HLL.from_enumerable(["a", "b", "c"], p: 10) iex> ExDataSketch.HLL.estimate(sketch) > 0.0 true # `merge` ```elixir @spec merge(t(), t()) :: t() ``` Merges two HLL 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.HLL.new(p: 10) |> ExDataSketch.HLL.update("x") iex> b = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("y") iex> merged = ExDataSketch.HLL.merge(a, b) iex> ExDataSketch.HLL.estimate(merged) >= ExDataSketch.HLL.estimate(a) true # `merge_many` ```elixir @spec merge_many(Enumerable.t()) :: t() ``` Merges a non-empty enumerable of HLL sketches into one. Raises `Enum.EmptyError` if the enumerable is empty. ## Examples iex> a = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("x") iex> b = ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.update("y") iex> merged = ExDataSketch.HLL.merge_many([a, b]) iex> ExDataSketch.HLL.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.HLL.merger(), 2) true # `new` ```elixir @spec new(keyword()) :: t() ``` Creates a new HLL 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). - `: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. ## Examples iex> sketch = ExDataSketch.HLL.new(p: 10) iex> sketch.opts[:p] 10 iex> ExDataSketch.HLL.size_bytes(sketch) 1028 # `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.HLL.reducer(), 2) true # `serialize` ```elixir @spec serialize( t(), keyword() ) :: binary() ``` Serializes the sketch to the ExDataSketch-native EXSK binary format. As of `ex_data_sketch` v0.8.0 the produced frame is **EXSK v2**: a versioned, CRC32C-checked binary wrapping the sketch's params and state together with an `ExDataSketch.Hash.Metadata` block recording the exact hashing identity used to produce the sketch. v1 frames remain decodable via `deserialize/1`. See `ExDataSketch.Binary` for the high-level frame contract and `ExDataSketch.Binary.Header` for the byte-level layout. Accepts an optional keyword list with the following keys: - `: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.HLL.new(p: 10) iex> binary = ExDataSketch.HLL.serialize(sketch) iex> <<"EXSK", 2, _rest::binary>> = binary iex> byte_size(binary) > 0 true iex> sketch = ExDataSketch.HLL.new(p: 10, hash_strategy: :phash2) iex> binary = ExDataSketch.HLL.serialize(sketch, format: :v1) iex> <<"EXSK", 1, 1, _rest::binary>> = binary # `serialize_datasketches` ```elixir @spec serialize_datasketches(t()) :: binary() ``` Serializes the sketch to Apache DataSketches HLL format. Not implemented. Apache DataSketches HLL interop is planned for v0.11.0 (blocked on hash-function equality between `ExDataSketch.Hash.hash64/1` and DataSketches' HLL union of LIST/SET/HLL_4/6/8 encodings). Only Theta and KLL sketches support DataSketches interop today, via `ExDataSketch.Theta.serialize_datasketches/1` and `ExDataSketch.KLL.serialize_datasketches/2`. For HLL serialization, use `serialize/1` (ExDataSketch-native EXSK format). ## Examples iex> try do ...> sketch = %ExDataSketch.HLL{state: <<>>, opts: [p: 14], backend: nil} ...> ExDataSketch.HLL.serialize_datasketches(sketch) ...> rescue ...> e in ExDataSketch.Errors.NotImplementedError -> e.message ...> end "ExDataSketch.HLL.serialize_datasketches is not yet implemented" # `size_bytes` ```elixir @spec size_bytes(t()) :: non_neg_integer() ``` Returns the size of the sketch state in bytes. ## Examples iex> ExDataSketch.HLL.new(p: 10) |> ExDataSketch.HLL.size_bytes() 1028 # `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.HLL.new(p: 10) |> ExDataSketch.HLL.update("hello") iex> ExDataSketch.HLL.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.HLL.new(p: 10) |> ExDataSketch.HLL.update_many(["a", "b", "c"]) iex> ExDataSketch.HLL.estimate(sketch) > 0.0 true --- *Consult [api-reference.md](api-reference.md) for complete listing*