Behaviour defining the computation backend for ExDataSketch.
All sketch computations are dispatched through a backend module. This abstraction allows swapping between the pure Elixir implementation and an optional Rust NIF backend without changing the public API.
Implementing a Backend
A backend module must implement all callbacks defined in this behaviour. The canonical sketch state is always an Elixir binary. Backend functions receive and return binaries; they never own persistent sketch state.
Available Backends
ExDataSketch.Backend.Pure-- Pure Elixir (always available, default).ExDataSketch.Backend.Rust-- Rust NIF acceleration (optional). Accelerates batch operations (update_many,merge,estimate). Falls back to Pure if the NIF is not compiled. Check withExDataSketch.Backend.Rust.available?/0.
Backend Selection
The backend is resolved in this order:
- Per-sketch
:backendoption (e.g.,HLL.new(backend: Backend.Rust)). - Application config:
config :ex_data_sketch, backend: Backend.Pure. - Default:
ExDataSketch.Backend.Pure.
Summary
Callbacks
Return the number of set bits (popcount) in Bloom state.
Test membership of a single hash64 value in Bloom state.
Merge two Bloom state binaries (bitwise OR of bitsets).
Create a new Bloom filter state binary with the given options.
Update Bloom state by setting bit positions for a single hash64 value.
Update Bloom state by setting bit positions for a list of hash64 values.
Estimate the count for a given hash64 from CMS state.
Merge two CMS state binaries (element-wise add).
Create a new CMS state binary with the given options.
Update CMS state with a single hash64 and increment.
Update CMS state with a list of {hash64, increment} pairs.
Return the total count of all items from CQF state (sum of multiplicities).
Delete a single occurrence of hash64 from CQF state (decrement count).
Return the estimated count of a single hash64 in CQF state.
Test membership of a single hash64 value in CQF state.
Merge two CQF state binaries (multiset union: counts summed).
Create a new CQF state binary with the given options.
Insert a single hash64 into CQF state, incrementing its count.
Insert a list of hash64 values into CQF state.
Return the number of stored items from Cuckoo state.
Delete a single hash64 from Cuckoo state. Returns {:ok, state} or {:error, :not_found}.
Test membership of a single hash64 value in Cuckoo state.
Create a new Cuckoo filter state binary with the given options.
Insert a single hash64 into Cuckoo state. Returns {:ok, state} or {:error, :full}.
Insert a list of hash64 values into Cuckoo state. Returns {:ok, state} or {:error, :full, state}.
Return the count of items inserted into DDSketch state.
Return the maximum value in DDSketch state, or nil if empty.
Merge two DDSketch state binaries.
Return the minimum value in DDSketch state, or nil if empty.
Create a new DDSketch state binary with the given options.
Return the approximate value at a given normalized rank from DDSketch state.
Return the approximate normalized rank of a given value from DDSketch state.
Update DDSketch state with a single float64 value.
Update DDSketch state with a list of float64 values in a single pass.
Return the total count of observed items from FrequentItems state.
Return the number of distinct tracked entries from FrequentItems state.
Return the frequency estimate for a given item_bytes from FrequentItems state.
Merge two FrequentItems state binaries.
Create a new FrequentItems state binary with the given options.
Return the top-k entries sorted by count descending from FrequentItems state.
Update FrequentItems state with a single item_bytes value.
Update FrequentItems state with a list of item_bytes values in a single pass.
Estimate cardinality from HLL state.
Merge two HLL state binaries (register-wise max).
Create a new HLL state binary with the given options.
Update HLL state with a single hash64 value.
Update HLL state with a list of hash64 values in a single pass.
Return the item count from IBLT state.
Delete a key_hash and value_hash from IBLT state.
List entries by peeling the IBLT. Returns {:ok, entries} or {:error, :decode_failed}.
Test membership of a single key_hash in IBLT state.
Merge two IBLT state binaries cell-wise (set union).
Create a new IBLT state binary with the given options.
Insert a key_hash and value_hash into IBLT state.
Insert a list of {key_hash, value_hash} pairs into IBLT state.
Subtract two IBLT state binaries cell-wise (set difference).
Return the CDF at the given split points from KLL state.
Return the count of items inserted into KLL state.
Return the maximum value in KLL state, or nil if empty.
Merge two KLL state binaries.
Return the minimum value in KLL state, or nil if empty.
Create a new KLL state binary with the given options.
Return the PMF at the given split points from KLL state.
Return the approximate value at a given normalized rank from KLL state.
Return the approximate normalized rank of a given value from KLL state.
Update KLL state with a single float64 value.
Update KLL state with a list of float64 values in a single pass.
Return the total count of observed items from MisraGries state.
Return the number of distinct tracked entries from MisraGries state.
Return the frequency estimate for a given item_bytes from MisraGries state.
Merge two MisraGries state binaries.
Create a new MisraGries state binary with the given options.
Return the top-k entries sorted by count descending from MisraGries state.
Update MisraGries state with a single item_bytes value.
Update MisraGries state with a list of item_bytes values in a single pass.
Return the number of stored items from Quotient state.
Delete a single hash64 from Quotient state.
Test membership of a single hash64 value in Quotient state.
Merge two Quotient state binaries.
Create a new Quotient filter state binary with the given options.
Insert a single hash64 into Quotient state.
Insert a list of hash64 values into Quotient state.
Return the CDF at the given split points from REQ state.
Return the count of items inserted into REQ state.
Return the maximum value in REQ state, or nil if empty.
Merge two REQ state binaries.
Return the minimum value in REQ state, or nil if empty.
Create a new REQ state binary with the given options.
Return the PMF at the given split points from REQ state.
Return the approximate value at a given normalized rank from REQ state.
Return the approximate normalized rank of a given value from REQ state.
Update REQ state with a single float64 value.
Update REQ state with a list of float64 values in a single pass.
Compact Theta state: sort entries and discard any above theta.
Estimate cardinality from Theta state.
Build Theta state binary from raw components (k, theta, sorted entries list).
Merge two Theta state binaries (set union).
Create a new Theta state binary with the given options.
Update Theta state with a single hash64 value.
Update Theta state with a list of hash64 values in a single pass.
Estimate cardinality from ULL state.
Merge two ULL state binaries (register-wise max).
Create a new ULL state binary with the given options.
Update ULL state with a single hash64 value.
Update ULL state with a list of hash64 values in a single pass.
Build an XorFilter from a list of hash64 values. Returns {:ok, state} or {:error, :build_failed}.
Return the number of items the XorFilter was built from.
Test membership of a single hash64 value in XorFilter state.
Functions
Returns the default backend module.
Resolves the backend from options or application config.
Types
Callbacks
@callback bloom_count(state_bin(), opts()) :: non_neg_integer()
Return the number of set bits (popcount) in Bloom state.
Test membership of a single hash64 value in Bloom state.
Merge two Bloom state binaries (bitwise OR of bitsets).
Create a new Bloom filter state binary with the given options.
Update Bloom state by setting bit positions for a single hash64 value.
Update Bloom state by setting bit positions for a list of hash64 values.
@callback cms_estimate(state_bin(), hash64(), opts()) :: non_neg_integer()
Estimate the count for a given hash64 from CMS state.
Merge two CMS state binaries (element-wise add).
Create a new CMS state binary with the given options.
@callback cms_update(state_bin(), hash64(), pos_integer(), opts()) :: state_bin()
Update CMS state with a single hash64 and increment.
@callback cms_update_many(state_bin(), [{hash64(), pos_integer()}], opts()) :: state_bin()
Update CMS state with a list of {hash64, increment} pairs.
@callback cqf_count(state_bin(), opts()) :: non_neg_integer()
Return the total count of all items from CQF state (sum of multiplicities).
Delete a single occurrence of hash64 from CQF state (decrement count).
@callback cqf_estimate_count(state_bin(), hash64(), opts()) :: non_neg_integer()
Return the estimated count of a single hash64 in CQF state.
Test membership of a single hash64 value in CQF state.
Merge two CQF state binaries (multiset union: counts summed).
Create a new CQF state binary with the given options.
Insert a single hash64 into CQF state, incrementing its count.
Insert a list of hash64 values into CQF state.
@callback cuckoo_count(state_bin(), opts()) :: non_neg_integer()
Return the number of stored items from Cuckoo state.
Delete a single hash64 from Cuckoo state. Returns {:ok, state} or {:error, :not_found}.
Test membership of a single hash64 value in Cuckoo state.
Create a new Cuckoo filter state binary with the given options.
Insert a single hash64 into Cuckoo state. Returns {:ok, state} or {:error, :full}.
@callback cuckoo_put_many(state_bin(), [hash64()], opts()) :: {:ok, state_bin()} | {:error, :full, state_bin()}
Insert a list of hash64 values into Cuckoo state. Returns {:ok, state} or {:error, :full, state}.
@callback ddsketch_count(state_bin(), opts()) :: non_neg_integer()
Return the count of items inserted into DDSketch state.
Return the maximum value in DDSketch state, or nil if empty.
Merge two DDSketch state binaries.
Return the minimum value in DDSketch state, or nil if empty.
Create a new DDSketch state binary with the given options.
Return the approximate value at a given normalized rank from DDSketch state.
Return the approximate normalized rank of a given value from DDSketch state.
Update DDSketch state with a single float64 value.
Update DDSketch state with a list of float64 values in a single pass.
@callback fi_count(state_bin(), opts()) :: non_neg_integer()
Return the total count of observed items from FrequentItems state.
@callback fi_entry_count(state_bin(), opts()) :: non_neg_integer()
Return the number of distinct tracked entries from FrequentItems state.
Return the frequency estimate for a given item_bytes from FrequentItems state.
Merge two FrequentItems state binaries.
Create a new FrequentItems state binary with the given options.
@callback fi_top_k(state_bin(), non_neg_integer(), opts()) :: [map()]
Return the top-k entries sorted by count descending from FrequentItems state.
Update FrequentItems state with a single item_bytes value.
Update FrequentItems state with a list of item_bytes values in a single pass.
Estimate cardinality from HLL state.
Merge two HLL state binaries (register-wise max).
Create a new HLL state binary with the given options.
Update HLL state with a single hash64 value.
Update HLL state with a list of hash64 values in a single pass.
@callback iblt_count(state_bin(), opts()) :: non_neg_integer()
Return the item count from IBLT state.
Delete a key_hash and value_hash from IBLT state.
@callback iblt_list_entries(state_bin(), opts()) :: {:ok, %{positive: [{hash64(), hash64()}], negative: [{hash64(), hash64()}]}} | {:error, :decode_failed}
List entries by peeling the IBLT. Returns {:ok, entries} or {:error, :decode_failed}.
Test membership of a single key_hash in IBLT state.
Merge two IBLT state binaries cell-wise (set union).
Create a new IBLT state binary with the given options.
Insert a key_hash and value_hash into IBLT state.
Insert a list of {key_hash, value_hash} pairs into IBLT state.
Subtract two IBLT state binaries cell-wise (set difference).
Return the CDF at the given split points from KLL state.
@callback kll_count(state_bin(), opts()) :: non_neg_integer()
Return the count of items inserted into KLL state.
Return the maximum value in KLL state, or nil if empty.
Merge two KLL state binaries.
Return the minimum value in KLL state, or nil if empty.
Create a new KLL state binary with the given options.
Return the PMF at the given split points from KLL state.
Return the approximate value at a given normalized rank from KLL state.
Return the approximate normalized rank of a given value from KLL state.
Update KLL state with a single float64 value.
Update KLL state with a list of float64 values in a single pass.
@callback mg_count(state_bin(), opts()) :: non_neg_integer()
Return the total count of observed items from MisraGries state.
@callback mg_entry_count(state_bin(), opts()) :: non_neg_integer()
Return the number of distinct tracked entries from MisraGries state.
@callback mg_estimate(state_bin(), binary(), opts()) :: non_neg_integer()
Return the frequency estimate for a given item_bytes from MisraGries state.
Merge two MisraGries state binaries.
Create a new MisraGries state binary with the given options.
@callback mg_top_k(state_bin(), non_neg_integer(), opts()) :: [ {binary(), non_neg_integer()} ]
Return the top-k entries sorted by count descending from MisraGries state.
Update MisraGries state with a single item_bytes value.
Update MisraGries state with a list of item_bytes values in a single pass.
@callback quotient_count(state_bin(), opts()) :: non_neg_integer()
Return the number of stored items from Quotient state.
Delete a single hash64 from Quotient state.
Test membership of a single hash64 value in Quotient state.
Merge two Quotient state binaries.
Create a new Quotient filter state binary with the given options.
Insert a single hash64 into Quotient state.
Insert a list of hash64 values into Quotient state.
Return the CDF at the given split points from REQ state.
@callback req_count(state_bin(), opts()) :: non_neg_integer()
Return the count of items inserted into REQ state.
Return the maximum value in REQ state, or nil if empty.
Merge two REQ state binaries.
Return the minimum value in REQ state, or nil if empty.
Create a new REQ state binary with the given options.
Return the PMF at the given split points from REQ state.
Return the approximate value at a given normalized rank from REQ state.
Return the approximate normalized rank of a given value from REQ state.
Update REQ state with a single float64 value.
Update REQ state with a list of float64 values in a single pass.
Compact Theta state: sort entries and discard any above theta.
Estimate cardinality from Theta state.
@callback theta_from_components(non_neg_integer(), non_neg_integer(), [non_neg_integer()]) :: state_bin()
Build Theta state binary from raw components (k, theta, sorted entries list).
Merge two Theta state binaries (set union).
Create a new Theta state binary with the given options.
Update Theta state with a single hash64 value.
Update Theta state with a list of hash64 values in a single pass.
Estimate cardinality from ULL state.
Merge two ULL state binaries (register-wise max).
Create a new ULL state binary with the given options.
Update ULL state with a single hash64 value.
Update ULL state with a list of hash64 values in a single pass.
Build an XorFilter from a list of hash64 values. Returns {:ok, state} or {:error, :build_failed}.
@callback xor_count(state_bin(), opts()) :: non_neg_integer()
Return the number of items the XorFilter was built from.
Test membership of a single hash64 value in XorFilter state.
Functions
@spec default() :: module()
Returns the default backend module.
Checks application config first, falls back to ExDataSketch.Backend.Pure.
Examples
iex> backend = ExDataSketch.Backend.default()
iex> backend == ExDataSketch.Backend.Pure
trueResolves the backend from options or application config.
Examples
iex> ExDataSketch.Backend.resolve(backend: ExDataSketch.Backend.Pure)
ExDataSketch.Backend.Pure
iex> ExDataSketch.Backend.resolve([])
ExDataSketch.Backend.Pure