ExDataSketch.DataSketches.KLLSketch (ExDataSketch v0.10.0)

Copy Markdown View Source

Apache DataSketches KLL binary codec for ExDataSketch.KLL.

This module encodes and decodes the compact KllFloatsSketch/ KllDoublesSketch binary format used by Apache DataSketches (Java, C++, Python) for cross-language interoperability.

Value Semantics

Unlike ExDataSketch.DataSketches.CompactSketch (Theta), KLL does not hash its inputs -- it stores the raw numeric values directly. This means KLL interop is a full item-level round trip: a sketch built by Apache DataSketches and decoded here (or vice versa) answers quantile/2, rank/2, min_value/1, and max_value/1 queries using the exact same retained values the other implementation would, with no hash-equality caveat to worry about.

Float vs. Double

Apache's on-disk format does not self-describe whether the sketch holds float (4-byte) or double (8-byte) items -- the caller must know in advance which variant they're working with, exactly as the Java API requires picking KllFloatsSketch or KllDoublesSketch explicitly. Pass variant: :float or variant: :double (default) accordingly; a wrong guess will usually (not always) surface as a DeserializationError because the item width shifts the expected binary layout.

Supported Features

  • Compact format only: reads and writes the compact, read-only representation. The "updatable" structure (SerVer == 3) is rejected.
  • Default M only: Apache's minimum-level-capacity parameter M must be the default (8) -- the only value ExDataSketch.KLL itself ever produces or expects.
  • KLL_FLOATS_SKETCH/KLL_DOUBLES_SKETCH family only: the KLL LONGS_SKETCH/ITEMS_SKETCH variants are out of scope.
  • All modes: empty, single-item, and full (n > 1) are supported.

Binary Layout

Little-endian, native byte order for multi-byte fields.

StructureSerVerPreIntsLayout
Compact Empty128-byte preamble only
Compact Single228-byte preamble + 1 item
Compact Full (n > 1)1520-byte preamble + levels array + min + max + items

Preamble bytes 0-7 (shared by all three structures):

byte 0: PreambleInts   byte 1: SerVer   byte 2: FamilyID (15)
byte 3: Flags          byte 4-5: K (u16)   byte 6: M (u8, must be 8)
byte 7: unused

Full-only, bytes 8-19: N (u64), MinK (u16), NumLevels (u8), unused byte. Then at byte 20: LevelsArr (NumLevels x signed i32 -- not NumLevels + 1; the top boundary is implied by the total binary length, since the compact form has no free space), followed by MinItem, MaxItem, then the items array itself, packed level-major (level 0 first).

Summary

Functions

decode(binary, opts \\ [])

Decodes an Apache DataSketches KLL compact binary into sketch components.

encode(kll, encode_opts \\ [])

Encodes an ExDataSketch.KLL sketch into the Apache DataSketches KLL compact binary format.

Functions

decode(binary, opts \\ [])

@spec decode(
  binary(),
  keyword()
) :: {:ok, map()} | {:error, Exception.t()}

Decodes an Apache DataSketches KLL compact binary into sketch components.

Returns {:ok, %{k: k, n: n, min_val: v, max_val: v, levels: [[float()]]}} (levels list-of-lists, level 0 first) or {:error, %DeserializationError{}}.

Options

  • :variant - :float or :double (default: :double). Must match the variant the binary was originally produced as -- see "Float vs. Double" in the moduledoc.

encode(kll, encode_opts \\ [])

@spec encode(
  ExDataSketch.KLL.t(),
  keyword()
) :: binary()

Encodes an ExDataSketch.KLL sketch into the Apache DataSketches KLL compact binary format.

Options

  • :variant - :float or :double (default: :double).