ExDataSketch.Quotient (ExDataSketch v0.10.0)

Quotient filter for probabilistic membership testing with safe deletion and merge.

A Quotient filter is a compact approximate membership data structure that splits a fingerprint into a quotient (slot index) and remainder (stored value). It supports insertion, safe deletion, membership queries, and merge without re-hashing.

Parameters

:q -- quotient bits (default: 16). Determines the number of slots: 2^q.
:r -- remainder bits (default: 8). Determines false positive rate: ~1/2^r. Constraint: q + r <= 64.
:seed -- hash seed (default: 0).

False Positive Rates

r bits	FPR
4	~6.25%
8	~0.39%
12	~0.024%
16	~0.0015%

Hash Strategy

Items are hashed via ExDataSketch.Hash.hash64/1 at the API boundary. The upper q bits of the 64-bit hash are the quotient (slot index). The next r bits are the remainder (stored value).

Merge Properties

Quotient filter merge is commutative and associative. The sortable property of the slot array enables merge via sorted fingerprint extraction and merge-sort without re-hashing the original items. Two filters can merge only if they have identical q, r, and seed.

Deletion Safety

Unlike Cuckoo filters, Quotient filter deletion is safe: deleting a non-inserted item is a no-op and does not create false negatives for other items.

Binary State Layout (QOT1)

32-byte header followed by a packed slot array. Each slot contains 3 metadata bits (is_occupied, is_continuation, is_shifted) and r remainder bits, packed LSB-first.

Summary

Types

t()

Functions

capabilities()

Returns the set of capabilities supported by Quotient filter.

compatible_with?(quotient1, quotient2)

Returns true if two Quotient filters have compatible parameters.

count(quotient)

Returns the number of items stored in the filter.

delete(qf, item)

Deletes a single item from the filter.

deserialize(binary)

Deserializes an EXSK binary into a Quotient filter.

from_enumerable(enumerable, opts \\ [])

Creates a Quotient filter from an enumerable of items.

member?(quotient, item)

Tests whether an item may be a member of the set.

merge(qf, quotient)

Merges two Quotient filters via sorted fingerprint merge.

merge_many(filters)

Merges a non-empty enumerable of Quotient filters into one.

merger(opts \\ [])

Returns a 2-arity merge function for combining filters.

new(opts \\ [])

Creates a new empty Quotient filter.

put(qf, item)

Inserts a single item into the filter.

put_many(qf, items)

Inserts multiple items in a single pass.

reducer()

Returns a 2-arity reducer function for use with Enum.reduce/3.

serialize(quotient, serialize_opts \\ [])

Serializes the filter to the EXSK binary format.

size_bytes(quotient)

Returns the byte size of the state binary.

update(qf, item)

Alias for put/2, added so ExDataSketch.Quotient satisfies the ExDataSketch.Sketch behaviour's generic update/2 callback.

update_many(qf, items)

Alias for put_many/2, added so ExDataSketch.Quotient satisfies the ExDataSketch.Sketch behaviour's generic update_many/2 callback.

Types

t()

@type t() :: %ExDataSketch.Quotient{
  backend: module(),
  opts: keyword(),
  state: binary()
}

Functions

capabilities()

Returns the set of capabilities supported by Quotient filter.

compatible_with?(quotient1, quotient2)

@spec compatible_with?(t(), t()) :: boolean()

Returns true if two Quotient filters have compatible parameters.

Examples

iex> a = ExDataSketch.Quotient.new(q: 10, r: 8)
iex> b = ExDataSketch.Quotient.new(q: 10, r: 8)
iex> ExDataSketch.Quotient.compatible_with?(a, b)
true

count(quotient)

@spec count(t()) :: non_neg_integer()

Returns the number of items stored in the filter.

Examples

iex> ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.count()
0

delete(qf, item)

@spec delete(t(), term()) :: t()

Deletes a single item from the filter.

Unlike Cuckoo filters, this operation is safe: deleting a non-member is a no-op and does not create false negatives.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
iex> qf = ExDataSketch.Quotient.delete(qf, "hello")
iex> ExDataSketch.Quotient.member?(qf, "hello")
false

deserialize(binary)

@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}

Deserializes an EXSK binary into a Quotient filter.

Returns {:ok, quotient} on success or {:error, reason} on failure.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("test")
iex> {:ok, recovered} = ExDataSketch.Quotient.deserialize(ExDataSketch.Quotient.serialize(qf))
iex> ExDataSketch.Quotient.member?(recovered, "test")
true

from_enumerable(enumerable, opts \\ [])

@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: t()

Creates a Quotient filter from an enumerable of items.

Equivalent to new(opts) |> put_many(enumerable).

Examples

iex> qf = ExDataSketch.Quotient.from_enumerable(["a", "b", "c"])
iex> ExDataSketch.Quotient.member?(qf, "a")
true

member?(quotient, item)

@spec member?(t(), term()) :: boolean()

Tests whether an item may be a member of the set.

Returns true if the item is possibly in the set (may be a false positive), false if the item is definitely not in the set.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
iex> ExDataSketch.Quotient.member?(qf, "hello")
true

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8)
iex> ExDataSketch.Quotient.member?(qf, "hello")
false

merge(qf, quotient)

@spec merge(t(), t()) :: t()

Merges two Quotient filters via sorted fingerprint merge.

Both filters must have identical q, r, and seed. Raises ExDataSketch.Errors.IncompatibleSketchesError if parameters differ.

Examples

iex> a = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("x")
iex> b = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("y")
iex> merged = ExDataSketch.Quotient.merge(a, b)
iex> ExDataSketch.Quotient.member?(merged, "x") and ExDataSketch.Quotient.member?(merged, "y")
true

merge_many(filters)

@spec merge_many(Enumerable.t()) :: t()

Merges a non-empty enumerable of Quotient filters into one.

Examples

iex> filters = Enum.map(1..3, fn i ->
...>   ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("item_#{i}")
...> end)
iex> merged = ExDataSketch.Quotient.merge_many(filters)
iex> ExDataSketch.Quotient.member?(merged, "item_1")
true

merger(opts \\ [])

@spec merger(keyword()) :: (t(), t() -> t())

Returns a 2-arity merge function for combining filters.

Examples

iex> is_function(ExDataSketch.Quotient.merger(), 2)
true

new(opts \\ [])

@spec new(keyword()) :: t()

Creates a new empty Quotient filter.

Options

:q -- quotient bits (default: 16). Range: 1..28.
:r -- remainder bits (default: 8). Range: 1..32. Constraint: q + r <= 64.
:seed -- hash seed (default: 0).
:backend -- backend module (default: ExDataSketch.Backend.Pure).
:hash_fn -- custom hash function (term -> non_neg_integer).

Examples

iex> qf = ExDataSketch.Quotient.new()
iex> qf.opts[:q]
16

iex> qf = ExDataSketch.Quotient.new(q: 12, r: 10)
iex> qf.opts[:r]
10

put(qf, item)

@spec put(t(), term()) :: t()

Inserts a single item into the filter.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
iex> ExDataSketch.Quotient.member?(qf, "hello")
true

put_many(qf, items)

@spec put_many(t(), Enumerable.t()) :: t()

Inserts multiple items in a single pass.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put_many(["a", "b"])
iex> ExDataSketch.Quotient.member?(qf, "a")
true

reducer()

@spec reducer() :: (term(), t() -> t())

Returns a 2-arity reducer function for use with Enum.reduce/3.

Examples

iex> is_function(ExDataSketch.Quotient.reducer(), 2)
true

serialize(quotient, serialize_opts \\ [])

@spec serialize(
  t(),
  keyword()
) :: binary()

Serializes the filter to the EXSK binary format.

Options

: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 filters using :phash2 hash strategy.

Examples

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8)
iex> binary = ExDataSketch.Quotient.serialize(qf)
iex> <<"EXSK", _rest::binary>> = binary
iex> byte_size(binary) > 0
true

iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8, hash_strategy: :phash2)
iex> binary = ExDataSketch.Quotient.serialize(qf, format: :v1)
iex> <<"EXSK", 1, 9, _rest::binary>> = binary

size_bytes(quotient)

@spec size_bytes(t()) :: non_neg_integer()

Returns the byte size of the state binary.

Examples

iex> qf = ExDataSketch.Quotient.new()
iex> ExDataSketch.Quotient.size_bytes(qf) > 0
true

update(qf, item)

@spec update(t(), term()) :: t()

Alias for put/2, added so ExDataSketch.Quotient satisfies the ExDataSketch.Sketch behaviour's generic update/2 callback.

put/2 remains the family-idiomatic name and the one used throughout this module's own documentation; update/2 exists purely for cross-family generic code (see ExDataSketch.update/2).

Examples

iex> qf = ExDataSketch.Quotient.new() |> ExDataSketch.Quotient.update("hello")
iex> ExDataSketch.Quotient.member?(qf, "hello")
true

update_many(qf, items)

@spec update_many(t(), Enumerable.t()) :: t()

Alias for put_many/2, added so ExDataSketch.Quotient satisfies the ExDataSketch.Sketch behaviour's generic update_many/2 callback.

Examples

iex> qf = ExDataSketch.Quotient.new() |> ExDataSketch.Quotient.update_many(["a", "b", "c"])
iex> ExDataSketch.Quotient.member?(qf, "a")
true