v0.9.0 - Streaming Integrations

ExDataSketch v0.9.0 Release Notes

Release date: 2026-05-20
Theme: Streaming Integrations -- the BEAM-native streaming approximate analytics infrastructure layer.

Highlights

Stream and Collectable Integration

All 13 mergeable sketch types now implement the Collectable protocol and support lazy stream consumption via ExDataSketch.Stream:

# Lazy stream consumption
sketch = 1..100_000 |> Stream.map(&to_string/1) |> ExDataSketch.Stream.hll(p: 14)

# Collectable protocol
sketch = Enum.into(1..50_000, ExDataSketch.ULL.new(p: 14))

# Partitioned parallel reduction
sketch = ExDataSketch.Stream.reduce_partitioned(1..1_000_000, ExDataSketch.HLL, partitions: 8, p: 14)

Broadway, GenStage, and Flow

Production-grade integration for streaming pipelines:

• ExDataSketch.Broadway.accumulate/3 -- build sketches from Broadway message batches
• ExDataSketch.Broadway.PeriodicAggregator -- periodic accumulation with timer flush
• ExDataSketch.GenStage.SketchConsumer -- back-pressure-aware sketch accumulation
• ExDataSketch.GenStage.SketchProducer -- emit accumulated sketches on demand
• ExDataSketch.Flow.reduce/3 and merge/2 -- parallel partition-local reduction

Five Persistence Backends

Save, load, merge, and delete sketches with atomic operations:

# ETS (in-memory)
ExDataSketch.Storage.ETS.save(sketch, table, "daily:2024-01-15")
{:ok, loaded} = ExDataSketch.Storage.ETS.load(ExDataSketch.HLL, table, "daily:2024-01-15")
ExDataSketch.Storage.ETS.merge(partial, table, "daily:2024-01-15")  # atomic merge

# Also: DETS, CubDB, Mnesia, Ecto

Production-Grade Telemetry

Structured :telemetry events at batch boundaries with category-based enable/disable:

:telemetry.attach("my-handler", [:ex_data_sketch, :sketch, :ingest], fn _name, meas, meta, _ ->
  Logger.info("#{meta.sketch_type}: #{meas.count} items in #{meas.duration}ns")
end, nil)

# OpenTelemetry bridge (optional)
ExDataSketch.Telemetry.OpenTelemetry.setup()

ULL Accuracy Fix

UltraLogLog estimates with few registers now use linear counting correction (when zeros > 0) and large-range bias correction, improving accuracy from 62.5% error to 0.8% at p=8/n=1000.

v1 Serialization Escape Hatch

# Produce backward-compatible v0.7.x binary (requires :phash2 hash strategy)
binary = ExDataSketch.HLL.serialize(sketch, format: :v1)

Nine Production-Oriented Livebooks

From streaming cardinality to AI token analytics. See guides/livebooks.md for the recommended reading order.

Breaking Changes

None. All v0.8.0 APIs are fully backward compatible.

ULL estimate change: ULL estimates at very low cardinalities (p < 12, n < 500) may differ from v0.8.0. The v0.9.0 estimates are more accurate. Add tolerance for small cardinalities in tests.

New Dependencies

• :telemetry ~> 1.0 (required, was already a transitive dependency)
• :broadway, :flow, :cubdb, :ecto_sql, :opentelemetry_api (optional, only loaded when available)

Full Changelog

See CHANGELOG.md for the complete list of changes.

Upgrade Guide

From v0.8.0: No code changes required. Add {:ex_data_sketch, "~> 0.9.0"} to your dependencies.

New features are opt-in:

• Telemetry is enabled by default; disable with config :ex_data_sketch, telemetry_enabled: false
• Persistence backends are enabled when their runtime dependency is available
• Stream/Broadway/GenStage/Flow modules are available when their dependencies are loaded

v0.8.0 — Deterministic Foundations

ex_data_sketch v0.8.0 — Deterministic Foundations

Release date: 2026-05-12

v0.8.0 transforms ex_data_sketch from a collection of probabilistic algorithms into a production-grade probabilistic runtime for the BEAM. Zero new sketch families. Five phases of substrate investment.

Highlights

Deterministic Hashing (Phase 1)

Every sketch now shares a documented, validated, byte-stable hash layer. Hash.XXH3, Hash.Murmur3, Hash.Metadata, and Hash.Validation are new. HLL.new/1, ULL.new/1, Theta.new/1, and CMS.new/1 now honor a user-supplied :hash_strategy (:xxhash3 | :murmur3 | :phash2). The :murmur3 option was silently overridden in v0.7.x — this is now a behavior change: code that passed hash_strategy: :murmur3 will produce different estimates than before (correct ones, using Murmur3).

Binary Stability & Corruption Detection (Phase 2)

EXSK serialization bumps from v1 to v2. Every serialize/1 output now carries a CRC32C checksum and an embedded Hash.Metadata block. deserialize/1 transparently reads both v1 and v2. A 200-mutation bit-flip fuzz suite verifies that no single-bit corruption silently propagates. v0.7.x readers cannot read v2 frames.

Hot-Path Performance (Phase 3)

8 new Rust NIFs (_raw_h_nif family) dispatch hashing by algorithm byte, extending in-Rust hashing to Murmur3. XXH3 throughput remains 25–34 M items/sec at p=14; Murmur3 is within 8%. Legacy _raw_nif family preserved for v0.7.x binary stability.

Precompiled NIFs (Phase 4)

Windows x86_64 and ARM64 MSVC targets added. The matrix is now 8 targets x 2 NIF versions = 16 artifacts per release. mix test.nif_on / mix test.nif_off aliases handle local NIF-mode flips.

Property-Based Validation (Phase 5)

14 new StreamData properties lock monotonicity (HLL/ULL), error bounds, rank consistency (KLL/REQ), overestimation-only (CMS), and no-false-negative guarantees (Bloom/XorFilter/Cuckoo). Binary v2 corruption never silently produces a valid sketch.

Post-Release Fixes (since tag)

• #240 — EXSK v2 Header.decode/1 now rejects non-zero reserved flags with a structured DeserializationError, matching the documented v2 contract. Previously, frames with flags != 0 were silently accepted.
• #238 — serialize/1 on any Murmur3-configured sketch no longer crashes with CaseClauseError. The sketch-local hash_strategy_byte/1 encoders across HLL, ULL, Theta, and CMS now map :murmur3 to wire byte 3.
• #239 — Release docs and the checksum file are no longer git-tracked; plan docs are excluded from the Hex package.
• Credo lint: replaced chained Enum.map |> Enum.map with single passes, replaced list ++ [item] with prepend-and-reverse, replaced List.foldl with Enum.reduce, replaced List.last with pattern matching, removed fully-qualified module references, removed restatement comments, documented previously @doc false public helpers.

Wire Format

Sketch (empty)	v1 size	v2 size	Overhead
HLL p=4	18 B	50 B	+32 (2.8x)
HLL p=14	16,398 B	16,430 B	+32 (0.2%)
KLL k=200 (populated)	~3-5 KB	~3-5 KB	+32 (~1%)

For any sketch larger than ~1 KB, overhead is negligible.

Performance

Path (HLL p=14)	Throughput
Pure phash2	~1.7 M items/sec
Pure xxhash3	~1.9 M items/sec
Rust raw XXH3	~30 M items/sec
Rust raw_h Murmur3	~28 M items/sec

Test Suite

Metric	v0.7.1	v0.8.0
Tests (NIF on)	1,186	1,317
Doctests	169	202
Properties (NIF on)	152	171
Line coverage	88%	92.7%
Credo issues	0	0

Breaking Changes

1. EXSK v2 is one-way. v0.7.x readers cannot decode v2 frames. Stage your rollout: deploy v0.8.0 readers first, then producers.
2. :murmur3 is no longer silently overridden. Code that passed hash_strategy: :murmur3 (and got :xxhash3 in v0.7.x) will now actually use Murmur3. Estimates are still correct but differ from v0.7.x output for the same input.
3. Serialized binary format changes. The version byte shifts from 1 to 2. Tests asserting <<"EXSK", 1, ...>> must update to 2.

Migration

Most users need no code changes. Full guide: guides/v0.8.0_migration_notes.md (shipped in HexDocs).

# mix.exs
{:ex_data_sketch, "~> 0.8.0"}

For deployments that share persisted sketches across nodes:

1. Deploy v0.8.0 to all readers first. v0.8.0 reads both v1 and v2.
2. Verify reader stability for one deploy cycle.
3. Deploy v0.8.0 to producers. They now emit v2 frames.

Known Issues

• ULL accuracy at low p. Use p >= 12 for production. At p < 12 and high cardinality, estimates diverge significantly.
• HLL memory at high cardinality. Streaming 10M+ items into a single HLL allocates ~1.86 GB of transient BEAM state. Workaround: smaller chunk sizes.
• Windows ARM64 precompiled NIF has limited CI history. Fallback: EX_DATA_SKETCH_BUILD=1 mix deps.compile.
• Backend.default/0 returns Pure even when the Rust NIF is loaded. Opt in explicitly: backend: ExDataSketch.Backend.Rust.

Non-Goals for v0.8.0

No new sketch families. No Apache DataSketches interop beyond Theta CompactSketch. No streaming integrations (Broadway/Flow). No persistence layers (ETS/DETS/CubDB). No telemetry. No SIMD. No 6-bit register packing. No raw-NIF path for membership filters.

---

Full design docs: plans/0.8.0_architectural_summary.md, plans/0.8.0-risks.md, plans/0.8.0_migration_notes.md, plans/0.8.0_serialization_compatibility.md.

v0.7.1

ExDataSketch v0.7.1 Release Notes

Release date: 2026-03-23

Summary

v0.7.1 is a performance and correctness release that moves hash computation
into Rust NIF batch calls, adds configurable hash functions and seeds, fixes a
quotient filter wrap-around bug, and adds merge-time hash compatibility
validation across all hash-based sketches.

What's new in v0.7.1

NIF batch hashing (94.6% memory reduction)

The update_many path for HLL, ULL, Theta, and CMS previously hashed every
item in Elixir before sending packed hashes to the NIF. For 10M items this
created ~30M+ transient heap allocations (term_to_binary + xxhash3 NIF
bigint + binary encoding per item).

v0.7.1 sends raw item binaries directly to Rust via ListIterator for
zero-copy Erlang list iteration. Rust decodes items, hashes each with xxhash3
in-loop, and updates registers -- zero per-item Elixir heap allocation beyond
the initial list.

Items	Before (memory)	After (memory)	Reduction
100K	28 MB	1.5 MB	94.6%
1M	281 MB	15 MB	94.7%
10M	2.75 GB	148 MB	94.6%

The existing hash-based NIF path is preserved for custom :hash_fn users and
backward compatibility.

Custom hash functions and seeds (#198)

All four hash-based sketches (HLL, ULL, Theta, CMS) now accept :hash_fn and
:seed options:

# Custom seed for reproducible hashing
hll = ExDataSketch.HLL.new(seed: 42)

# Custom hash function (disables NIF batch path)
hll = ExDataSketch.HLL.new(hash_fn: fn item -> MyHash.hash(item) end)

Seed values are propagated through serialization/deserialization and validated
at merge time.

Merge hash-compatibility validation (#205)

merge/2 on HLL, ULL, Theta, and CMS now validates that both sketches use the
same hash strategy and seed. Merging sketches with different hashing
configurations raises IncompatibleSketchesError instead of producing silently
corrupted results:

a = ExDataSketch.HLL.new(seed: 1)
b = ExDataSketch.HLL.new(seed: 2)
ExDataSketch.HLL.merge(a, b)
# ** (ExDataSketch.Errors.IncompatibleSketchesError) HLL seed mismatch: 1 vs 2

Merging sketches with custom :hash_fn is explicitly rejected since hash
function compatibility cannot be verified at runtime.

Quotient filter wrap-around fix (#203, #204)

Both Pure and Rust backends had a bug in extract_all where clusters wrapping
from slot N-1 to slot 0 caused nil quotients (Pure crash) or silent data
corruption (Rust). The fix correctly tracks the current quotient across array
boundary wrap-around.

Pure backend optimizations

• HLL update_many: Pre-aggregate map with sorted binary splice replaces
  tuple-based per-hash full-tuple copies, reducing transient allocation from
  O(n * m) to O(n + m).
• Batch path restoration: HLL, ULL, and Theta Pure backend update_many
  restored to use chunk + batch *_update_many instead of per-item *_update.

Test infrastructure

• 39 new tests covering deserialization edge cases, custom hash_fn paths,
  Rust-only helper functions, and merge hash-compatibility validation.
• Configurable coverage baselines via EX_DATA_SKETCH_COVERAGE_BASELINE env
  var for separate pure-only and Rust CI coverage thresholds.
• Coverage reporting added to test-rust CI job.
• Hash-dependent vector tests tagged with @tag :rust_nif for correct
  pure-only CI behavior.

Closed Issues

• #198 -- Wire :hash_fn and :seed options through HLL, ULL, Theta, CMS
• #202 -- Move hashing into NIF batch calls via ListIterator
• #203 -- Quotient filter Pure backend wrap-around bug
• #204 -- Quotient filter Rust backend wrap-around bug
• #205 -- Merge hash-compatibility validation

Installation

def deps do
  [
    {:ex_data_sketch, "~> 0.7.1"}
  ]
end

Precompiled Rust NIF binaries are downloaded automatically on supported
platforms (macOS ARM64/x86_64, Linux x86_64/aarch64 glibc/musl). No Rust
toolchain required. The library works in pure Elixir mode on all other
platforms.

Upgrade Notes

• No breaking changes from v0.7.0.
• EXSK binaries produced by earlier v0.x releases remain fully compatible.
• Sketches serialized without a seed default to seed 0 on deserialization,
  preserving backward compatibility.
• The NIF batch hashing path is used automatically when no custom :hash_fn
  is set. Custom hash function users see no behavior change.
• CMS merge/2 now validates width, depth, and counter_width explicitly
  instead of comparing full option keyword lists.

What's Next

v0.8.0 directions under consideration include Binary Fuse Filters for even
smaller static membership filters, Ribbon Filters for space-optimal static
filters, and expanded Apache DataSketches interop for cross-language sketch
exchange.

Links

• HexDocs
• GitHub
• Changelog

v0.7.0

What's Changed

• V0.7.0/ultra log log by @thanos in #188

Full Changelog: v0.6.0...v0.7.0

v0.6.0

ExDataSketch v0.6.0 Release Notes

Release date: 2026-03-12

Summary

v0.6.0 adds two new sketch algorithms (REQ and Misra-Gries), integrates
XXHash3 as an opt-in hash function via Rust NIF, and delivers Rust NIF
acceleration for all six membership filters (Bloom, Cuckoo, Quotient, CQF,
XorFilter, IBLT). Every membership filter now has byte-identical parity between
the Pure Elixir and Rust NIF backends, verified by deterministic parity tests.

ExDataSketch now covers 16 sketch types across eight categories:

Category	Algorithms
Cardinality	HyperLogLog (HLL)
Frequency	Count-Min Sketch (CMS)
Set operations	Theta Sketch
Quantiles	KLL, DDSketch, REQ
Frequency ranking	FrequentItems (SpaceSaving), Misra-Gries
Membership	Bloom, Cuckoo, Quotient, CQF, XorFilter
Set reconciliation	IBLT
Composition	FilterChain

What's new in v0.6.0

REQ Sketch (ExDataSketch.REQ)

Relative-error quantile sketch with configurable accuracy bias. REQ provides
rank-proportional error: the relative error at rank r is bounded by
alpha * r (HRA mode) or alpha * (1-r) (LRA mode), making it ideal for
high-percentile monitoring where tail accuracy matters most.

Key features:

• High-rank accuracy (HRA) and low-rank accuracy (LRA) modes
• Configurable k parameter (accuracy vs memory tradeoff)
• quantile/2, quantiles/2, rank/2 queries
• Merge support for distributed aggregation
• REQ1 binary state format
• EXSK serialization (sketch ID 13)

Quick start:

req = ExDataSketch.REQ.new(k: 12, hra: true)
req = ExDataSketch.REQ.update_many(req, 1..100_000)

ExDataSketch.REQ.quantile(req, 0.99)   # 99th percentile with high accuracy
ExDataSketch.REQ.quantile(req, 0.999)  # 99.9th percentile
ExDataSketch.REQ.rank(req, 50_000.0)   # normalized rank of a value

Misra-Gries Sketch (ExDataSketch.MisraGries)

Deterministic heavy-hitter detection with guaranteed frequency thresholds.
Unlike the probabilistic FrequentItems (SpaceSaving), Misra-Gries provides
a hard guarantee: any item with true frequency exceeding n/k is tracked.

Key features:

• Deterministic guarantee: items above n/k frequency are always tracked
• Configurable key encoding: :binary, :int, {:term, :external}
• estimate/2 for per-item frequency lower bounds
• top_k/2 for ranked heavy hitters
• frequent/2 for threshold-based filtering
• Merge support
• MG01 binary state format
• EXSK serialization (sketch ID 14)

Quick start:

mg = ExDataSketch.MisraGries.new(k: 10)
mg = Enum.reduce(1..1000, mg, fn _, s -> ExDataSketch.MisraGries.update(s, "hot") end)
mg = Enum.reduce(1..100, mg, fn i, s -> ExDataSketch.MisraGries.update(s, "cold_#{i}") end)

ExDataSketch.MisraGries.top_k(mg, 5)       # [{"hot", 1000}, ...]
ExDataSketch.MisraGries.estimate(mg, "hot") # 1000

XXHash3 Integration (ExDataSketch.Hash)

XXHash3 is now available as an opt-in hash function, providing faster hashing
with better distribution than the default phash2-based hash. When the Rust NIF
is available, XXHash3 output is stable across platforms and OTP versions.

Key features:

• xxhash3_64/1 and xxhash3_64/2 (with seed)
• Rust NIF implementation for speed
• Automatic phash2-based fallback when NIF is unavailable
• Seeds are masked to u64 range for safe NIF interop
• Opt-in for backwards compatibility with existing serialized data

Quick start:

# Use XXHash3 as hash function for any sketch
hll = ExDataSketch.HLL.new(p: 14, hash_fn: &ExDataSketch.Hash.xxhash3_64/1)
hll = ExDataSketch.HLL.update_many(hll, ["alice", "bob", "carol"])
ExDataSketch.HLL.estimate(hll)

KLL cdf/pmf and DDSketch rank

• ExDataSketch.KLL.cdf/2 -- cumulative distribution function at split points
• ExDataSketch.KLL.pmf/2 -- probability mass function at split points
• ExDataSketch.DDSketch.rank/2 -- normalized rank of a value

Quantiles Facade (ExDataSketch.Quantiles)

Unified API for quantile sketches. Write algorithm-agnostic code that works
with either KLL or DDSketch:

sketch = ExDataSketch.Quantiles.new(type: :kll)
sketch = ExDataSketch.Quantiles.update_many(sketch, 1..10_000)
ExDataSketch.Quantiles.quantile(sketch, 0.5)
ExDataSketch.Quantiles.count(sketch)

Rust NIF Acceleration for Membership Filters

All six membership filters now have Rust NIF acceleration for batch operations.
The NIF backend is used automatically when available, with dirty scheduler
thresholds to avoid blocking normal schedulers on large inputs.

Filter	Accelerated operations	Dirty threshold
Bloom	put_many, merge	10,000 / 50,000 items
Cuckoo	put_many	10,000 items
Quotient	put_many, merge	10,000 / 50,000 items
CQF	put_many, merge	10,000 / 50,000 items
XorFilter	build	10,000 items
IBLT	put_many, merge	10,000 / 50,000 items

Both backends produce byte-identical serialized output for the same inputs,
verified by deterministic parity tests.

Benchmarks

New benchmark suites:

• bench/req_bench.exs -- REQ sketch operations
• bench/misra_gries_bench.exs -- Misra-Gries operations
• bench/xxhash3_bench.exs -- XXHash3 NIF throughput at various data sizes

Existing membership filter benchmarks now automatically show Pure vs Rust
comparison columns when the NIF is available.

Run all benchmarks with mix bench.

Algorithm Matrix

Algorithm	Purpose	EXSK ID	Backend
HLL	Cardinality estimation	1	Pure + Rust
CMS	Frequency estimation	2	Pure + Rust
Theta	Set operations	3	Pure + Rust
KLL	Rank/quantile/cdf/pmf	4	Pure + Rust
DDSketch	Value-relative quantiles/rank	5	Pure + Rust
FrequentItems	Probabilistic heavy-hitter detection	6	Pure + Rust
Bloom	Membership testing	7	Pure + Rust
Cuckoo	Membership with deletion	8	Pure + Rust
Quotient	Membership with deletion/merge	9	Pure + Rust
CQF	Multiset membership/counting	10	Pure + Rust
XorFilter	Static membership testing	11	Pure + Rust
IBLT	Set reconciliation	12	Pure + Rust
REQ	Relative-error quantiles	13	Pure
MisraGries	Deterministic heavy hitters	14	Pure
FilterChain	Filter composition	--	Pure
Quantiles	Quantile facade (KLL/DDSketch)	--	--

Installation

def deps do
  [
    {:ex_data_sketch, "~> 0.6.0"}
  ]
end

Precompiled Rust NIF binaries are downloaded automatically on supported
platforms (macOS ARM64/x86_64, Linux x86_64/aarch64 glibc/musl). No Rust
toolchain required. The library works in pure Elixir mode on all other
platforms.

Upgrade Notes

• No breaking changes from v0.5.0.
• EXSK binaries produced by earlier v0.x releases remain fully compatible.
• The ExDataSketch.Backend behaviour now includes additional callbacks for
  REQ and Misra-Gries. Custom backend implementations must add these callbacks.
• ExDataSketch.Quantiles no longer includes REQ in the facade (KLL and
  DDSketch only). REQ is accessed directly via ExDataSketch.REQ.
• Membership filter NIF acceleration is automatic and transparent. No code
  changes are needed to benefit from the Rust backend.
• The Quantiles.quantiles/2 typespec was tightened from
  [float() | nil] | nil to [float() | nil].

Rust NIF Safety Hardening

This release includes several safety improvements to the Rust NIF layer:

• All recursive traversals in quotient filter slot arithmetic converted to
  bounded iterative loops to prevent stack overflow
• shift_right bounded to at most slot_count iterations to prevent infinite
  loops on full/corrupt filter state
• Binary header validation before slicing in all NIF entry points to prevent
  out-of-bounds panics
• Parameter validation (zero bucket counts, out-of-range fingerprint bits) to
  prevent arithmetic overflow
• OwnedBinary::new() allocation failure returns error tuples instead of
  panicking
• XorFilter build uses deterministic deduplication (sort + dedup) and
  deterministic peeling order for cross-node reproducibility
• XorFilter seed retry uses wrapping addition to prevent u32 overflow panic
• MisraGries binary_to_term uses [:safe] option to prevent atom-table
  exhaustion from untrusted data

What's Next

v0.7.0 adds UltraLogLog (ULL), a next-generation cardinality estimation
sketch based on Ertl (2023). ULL delivers approximately 20% lower relative
error than HyperLogLog at the same memory footprint, with full Pure Elixir
and Rust NIF backends, EXSK serialization, and distributed merge support.

Links

• HexDocs
• GitHub
• Changelog

v0.5.0

Release date: 2026-03-11

Summary

v0.5.0 adds six new structures for advanced membership testing and set
reconciliation, plus FilterChain for composing filters into lifecycle-tier
pipelines. This is the largest feature release yet, bringing ExDataSketch to
13 sketch types across seven categories.

ExDataSketch now covers:

Category	Algorithms
Cardinality	HyperLogLog (HLL)
Frequency	Count-Min Sketch (CMS)
Set operations	Theta Sketch
Quantiles	KLL, DDSketch
Frequency ranking	FrequentItems (SpaceSaving)
Membership	Bloom, Cuckoo, Quotient, CQF, XorFilter
Set reconciliation	IBLT
Composition	FilterChain

What's new in v0.5.0

Cuckoo Filter (ExDataSketch.Cuckoo)

Membership testing with deletion support using partial-key cuckoo hashing.
Unlike Bloom filters, Cuckoo filters support safe deletion of previously
inserted items. Better space efficiency than Bloom at low false positive rates.

Key features:

• Partial-key cuckoo hashing with configurable fingerprint size (8, 12, 16 bits)
• Configurable bucket size (2 or 4 slots) and max kicks (100..2000)
• Safe deletion without false negatives on subsequent queries
• CKO1 binary state format
• EXSK serialization (sketch ID 8)

Quick start:

cuckoo = ExDataSketch.Cuckoo.new(capacity: 100_000, fingerprint_size: 8)

{:ok, cuckoo} = ExDataSketch.Cuckoo.put(cuckoo, "user_42")
ExDataSketch.Cuckoo.member?(cuckoo, "user_42")  # true

{:ok, cuckoo} = ExDataSketch.Cuckoo.delete(cuckoo, "user_42")
ExDataSketch.Cuckoo.member?(cuckoo, "user_42")  # false

Quotient Filter (ExDataSketch.Quotient)

Membership testing with safe deletion and merge. Splits fingerprints into
quotient (slot index) and remainder (stored value) with metadata bits for
cluster tracking. Supports merge without re-hashing.

Key features:

• Quotient/remainder fingerprint splitting with linear probing
• Metadata bits (is_occupied, is_continuation, is_shifted) for cluster tracking
• Safe deletion and merge support
• QOT1 binary state format
• EXSK serialization (sketch ID 9)

Quick start:

qf = ExDataSketch.Quotient.new(q: 16, r: 8)
qf = ExDataSketch.Quotient.put(qf, "item_a")
ExDataSketch.Quotient.member?(qf, "item_a")  # true

# Merge two quotient filters
merged = ExDataSketch.Quotient.merge(qf_a, qf_b)

Counting Quotient Filter (ExDataSketch.CQF)

Extends the quotient filter with variable-length counter encoding to answer
not just "is this present?" but "how many times was this inserted?" Counts are
approximate (never underestimated).

Key features:

• Variable-length counter encoding within runs
• estimate_count/2 for approximate multiplicity queries
• Safe deletion (decrements count)
• Merge sums counts across filters
• CQF1 binary state format
• EXSK serialization (sketch ID 10)

Quick start:

cqf = ExDataSketch.CQF.new(q: 16, r: 8)
cqf = ExDataSketch.CQF.put(cqf, "event_x")
cqf = ExDataSketch.CQF.put(cqf, "event_x")
cqf = ExDataSketch.CQF.put(cqf, "event_x")

ExDataSketch.CQF.estimate_count(cqf, "event_x")  # >= 3
ExDataSketch.CQF.member?(cqf, "event_x")          # true

XorFilter (ExDataSketch.XorFilter)

Static, immutable membership filter with the smallest footprint and fastest
lookups. All items must be provided at construction time via build/2.
No insertion, deletion, or merge -- query only.

Key features:

• Build-once immutable construction via build/2
• 8-bit or 16-bit fingerprints (configurable false positive rate)
• Smallest memory footprint of all membership filters
• XOR1 binary state format
• EXSK serialization (sketch ID 11)

Quick start:

items = MapSet.new(1..100_000)
{:ok, xor} = ExDataSketch.XorFilter.build(items, fingerprint_bits: 8)

ExDataSketch.XorFilter.member?(xor, 42)      # true
ExDataSketch.XorFilter.member?(xor, 999_999) # false (probably)

IBLT (ExDataSketch.IBLT)

Invertible Bloom Lookup Table for set reconciliation. Two parties each build
an IBLT from their sets, exchange them, and subtract to discover only the
differing items -- without transmitting the full sets.

Key features:

• Set mode (items only) and key-value mode
• subtract/2 for cell-wise difference
• list_entries/1 for peeling decoded entries (positive/negative sets)
• Merge via cell-wise addition
• IBL1 binary state format
• EXSK serialization (sketch ID 12)

Quick start:

# Set reconciliation between two nodes
iblt_a = ExDataSketch.IBLT.new(cell_count: 1000) |> ExDataSketch.IBLT.put_many(set_a)
iblt_b = ExDataSketch.IBLT.new(cell_count: 1000) |> ExDataSketch.IBLT.put_many(set_b)

diff = ExDataSketch.IBLT.subtract(iblt_a, iblt_b)
{:ok, %{positive: only_in_a, negative: only_in_b}} = ExDataSketch.IBLT.list_entries(diff)

FilterChain (ExDataSketch.FilterChain)

Capability-aware composition framework for chaining membership filters into
lifecycle-tier pipelines. Enforces valid chain positions based on each
filter's capabilities.

Key features:

• add_stage/2 with position validation (front/middle/terminal/adjunct)
• put/2 fans out to all stages supporting insertion (skips static stages)
• member?/2 queries stages in order, short-circuits on false
• Lifecycle-tier patterns: hot Cuckoo (writes) -> cold XorFilter (snapshots)
• IBLT stages placed as adjuncts (not in query path)
• FCN1 binary state format

Quick start:

chain =
  ExDataSketch.FilterChain.new()
  |> ExDataSketch.FilterChain.add_stage(ExDataSketch.Cuckoo.new(capacity: 10_000))
  |> ExDataSketch.FilterChain.add_stage(ExDataSketch.Bloom.new(capacity: 100_000))

{:ok, chain} = ExDataSketch.FilterChain.put(chain, "item_1")
ExDataSketch.FilterChain.member?(chain, "item_1")  # true

Benchmarks

Benchmark suites added for all new structures:

• bench/cuckoo_bench.exs
• bench/quotient_bench.exs
• bench/cqf_bench.exs
• bench/xor_filter_bench.exs
• bench/iblt_bench.exs
• bench/filter_chain_bench.exs

Run all benchmarks with mix bench.

Algorithm Matrix

Algorithm	Purpose	EXSK ID	Backend
HLL	Cardinality estimation	1	Pure + Rust
CMS	Frequency estimation	2	Pure + Rust
Theta	Set operations	3	Pure + Rust
KLL	Rank/quantile estimation	4	Pure + Rust
DDSketch	Value-relative quantiles	5	Pure + Rust
FrequentItems	Heavy-hitter detection	6	Pure + Rust
Bloom	Membership testing	7	Pure
Cuckoo	Membership with deletion	8	Pure
Quotient	Membership with deletion/merge	9	Pure
CQF	Multiset membership/counting	10	Pure
XorFilter	Static membership testing	11	Pure
IBLT	Set reconciliation	12	Pure
FilterChain	Filter composition	--	Pure

Installation

def deps do
  [
    {:ex_data_sketch, "~> 0.5.0"}
  ]
end

Precompiled Rust NIF binaries are downloaded automatically on supported
platforms (macOS ARM64/x86_64, Linux x86_64/aarch64 glibc/musl). No Rust
toolchain required. The library works in pure Elixir mode on all other
platforms.

Upgrade Notes

• No breaking changes from v0.4.0.
• EXSK binaries produced by earlier v0.x releases remain fully compatible.
• The ExDataSketch.Backend behaviour now includes additional callbacks for
  Cuckoo, Quotient, CQF, XorFilter, IBLT, and FilterChain. Custom backend
  implementations must add these callbacks.
• New error types: UnsupportedOperationError and InvalidChainCompositionError.
• All membership filter modules now export capabilities/0 returning a MapSet
  of supported operations.

What's Next

• v0.6.0 - Rust NIF acceleration for v0.5.0 structures, and advanced Quantiles
• v0.7.0 - advanced Cardinality Sketches including CPC, HLL++, ULL (UltraLogLog), SetSketch
• v0.8.0 scope is under discussion. Potential directions include Rust NIF
  acceleration for v0.5.0 structures, additional composition patterns, or
  new sketch types.

Links

• HexDocs
• GitHub
• Changelog

v0.4.0

Full Changelog: v0.3.0...v0.4.0

What's new in v0.4.0

Bloom filter:

• Automatic parameter derivation from capacity and false_positive_rate
• Double hashing (Kirsch-Mitzenmacher) for k bit positions from one hash
• BLM1 binary format (40-byte header + packed bitset)
• Merge via bitwise OR
• Capacity overflow validation for the u32 binary format constraints
• 40 unit tests, 5 property tests, 2 statistical FPR validation tests

Algorithm	What it does
HyperLogLog (HLL)	Count distinct elements (~0.8% error, 16 KB)
Count-Min Sketch (CMS)	Estimate item frequencies
Theta Sketch	Set union/intersection cardinality
KLL	Rank-accurate quantiles (median, P99)
DDSketch	Value-relative quantiles (P99 latency +/- 1%)
FrequentItems	Top-k most frequent items (SpaceSaving)
Bloom Filter	"Have I seen this before?" with tunable FPR

ExDataSketch v0.3.0 -- FrequentItems / Heavy-Hitters

ExDataSketch v0.3.0 -- FrequentItems / Heavy-Hitters

ExDataSketch v0.3.0 adds FrequentItems, a streaming heavy-hitter sketch based on the SpaceSaving algorithm. This is the sixth sketch family in the library and the first non-numeric sketch type.

What is FrequentItems?

FrequentItems tracks the approximate top-k most frequent items in a data stream using bounded memory. It maintains at most k counters, each storing an item, its estimated count, and a maximum overcount error. The SpaceSaving algorithm guarantees that any item whose true frequency exceeds N/k will always be tracked.

sketch =
  ExDataSketch.FrequentItems.new(k: 10)
  |> ExDataSketch.FrequentItems.update_many(stream_of_page_views)

# Get the top 5 most frequent items
ExDataSketch.FrequentItems.top_k(sketch, 5)
# [%{item: "/home", estimate: 4821, error: 12, lower: 4809, upper: 4821}, ...]

# Check a specific item
ExDataSketch.FrequentItems.estimate(sketch, "/checkout")
# {:ok, %{estimate: 312, error: 5, lower: 307, upper: 312}}

Highlights

Full Pure Elixir + Rust NIF dual-backend support

Like all ExDataSketch algorithms, FrequentItems ships with a pure Elixir implementation and optional Rust NIF acceleration. Both backends produce byte-identical serialized output for the same inputs.

Canonical FI1 binary state format

FrequentItems uses a 32-byte header followed by variable-length entries sorted by item bytes. The format is deterministic and portable across backends.

Flexible key encoding

Three key encoding modes are supported:

Encoding	Use case
:binary (default)	String keys, raw binary data
:int	Integer keys (signed 64-bit little-endian)
{:term, :external}	Arbitrary Erlang terms via :erlang.term_to_binary/1

Deterministic merge

FrequentItems merge is commutative. It combines counts additively across the union of keys, then replays weighted updates in sorted key order into an empty sketch. Count (n) is always exactly additive regardless of whether entries are dropped during capacity enforcement.

Smart NIF routing

Query operations (top_k, estimate) route to Rust only when k >= 256, where NIF acceleration outweighs the call boundary overhead. Header reads (count, entry_count) always use Pure Elixir since they are O(1) binary pattern matches.

Other changes

• Rust NIF for theta_compact with dirty scheduler support.
• Mox added as a test dependency for backend contract testing.
• EXSK codec sketch ID 6 for FrequentItems.

Upgrading

def deps do
  [
    {:ex_data_sketch, "~> 0.3.0"}
  ]
end

No breaking changes from v0.2.1. All existing sketches (HLL, CMS, Theta, KLL, DDSketch) are unchanged.

Algorithm coverage

Algorithm	Purpose	Status
HyperLogLog (HLL)	Cardinality estimation	Pure + Rust
Count-Min Sketch (CMS)	Frequency estimation	Pure + Rust
Theta Sketch	Set operations on cardinalities	Pure + Rust
KLL Quantiles	Rank and quantile estimation	Pure + Rust
DDSketch	Relative-error quantile estimation	Pure + Rust
FrequentItems (SpaceSaving)	Heavy-hitter detection	Pure + Rust

v0.2.1

What's Changed

• V0.2.1/dd sketch quantiles by @thanos in #101

Full Changelog: v0.2.0...v0.2.1

v0.2.0-alpha.1

What's Changed

• Deterministic vectors by @thanos in #76
• Add KLL quantiles sketch with Pure Elixir and Rust NIF backends by @thanos in #86

Full Changelog: v0.1.0-alpha.12...v0.2.0-alpha.1