Quotient Filter Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])

Introduction

ExDataSketch.Quotient splits each item's hash into two parts: the upper q bits (the quotient, which slot it belongs near) and the next r bits (the remainder, what actually gets stored). Items are kept in sorted order within their slot region, using three metadata bits per slot (is_occupied, is_continuation, is_shifted) to encode collisions without tombstones or chaining -- which is what makes both deletion and merging safe: a slot's neighbors always know exactly where they should be, so removing or combining entries can't silently orphan someone else's data:

flowchart LR
    A[item] --> B["hash(item)"]
    B --> C["quotient (upper q bits)\n= slot region"]
    B --> D["remainder (next r bits)\n= stored value"]
    C --> E["insert/find remainder in\nsorted run (metadata bits\ntrack occupied/shifted)"]
    D --> E

That structure gives Quotient both of the things ExDataSketch.Cuckoo trades off against each other: safe deletion (deleting a non-inserted item is guaranteed to be a no-op, never introducing a false negative for something else) and merge/2. The trade is sizing: capacity is set via :q/:r bit widths (2^q slots) rather than a plain item count, and false-positive rate is a function of :r alone.

Use it for: the one membership filter here that needs both safe deletion and merge/2 in the same structure -- Cuckoo has deletion but no merge; Bloom has merge but no deletion.

Don't use it for: cases needing the tightest possible bits per item -- Bloom and Cuckoo both pack tighter, since Quotient spends extra bits on the sorted-run metadata that makes deletion/merge safe. Also not for cases where you'd rather size by a plain expected item count -- Quotient's capacity is a 2^q slot-table bit-width choice, not a :capacity option the way Bloom/Cuckoo take directly.

What it buys you: at q: 19, r: 8 (524,288 slots, used throughout this tutorial), 300,000 API keys measured ~1 MB -- less dramatic savings than Bloom or Cuckoo's raw bits/item, but with a capability neither of them offers alone:

Approach	Memory (300,000 keys)	Delete?	Merge?
Exact set (raw key strings)	4+ MB (grows with item size)	Yes	N/A
`ExDataSketch.Quotient` (q=19,r=8)	~1 MB, fixed	Yes, safely	Yes

Sample data (cached locally)

{inserted, novel} = ExDataSketch.SampleData.quotient_api_keys()
IO.puts("#{length(inserted)} inserted keys, #{length(novel)} novel keys")

Basic usage

:q picks the slot count (2^q) -- q: 19 gives 524,288 slots, enough headroom for 300,000 items without excessive load:

alias ExDataSketch.Quotient

filter = Quotient.new(q: 19, r: 8) |> Quotient.put_many(inserted)

Quotient.member?(filter, hd(inserted))

Safe deletion

f = Quotient.new(q: 10, r: 8) |> Quotient.put("real_item")

# Deleting something never inserted is a safe no-op -- it does not
# disturb "real_item", unlike a naive Cuckoo-style eviction could.
f = Quotient.delete(f, "never_inserted")

IO.puts("real_item still present: #{Quotient.member?(f, "real_item")}")

No false negatives, measured false-positive rate

false_positives = Enum.count(novel, &Quotient.member?(filter, &1))
observed_fpr = false_positives / length(novel)
IO.puts("False positives: #{false_positives} / #{length(novel)} (#{Float.round(observed_fpr * 100, 4)}%)")

Sizing: r controls false-positive rate

for r <- [4, 8, 12] do
  f = Quotient.new(q: 19, r: r) |> Quotient.put_many(inserted)
  observed = Enum.count(Enum.take(novel, 50_000), &Quotient.member?(f, &1)) / 50_000
  IO.puts("r=#{r} (#{Quotient.size_bytes(f)} bytes): observed FPR=#{Float.round(observed * 100, 4)}%")
end

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

Merging

Both filters must share identical q, r, and seed:

half = div(length(inserted), 2)
{first_half, second_half} = Enum.split(inserted, half)

worker_a = Quotient.new(q: 19, r: 8) |> Quotient.put_many(first_half)
worker_b = Quotient.new(q: 19, r: 8) |> Quotient.put_many(second_half)

merged = Quotient.merge(worker_a, worker_b)
IO.puts("Merged contains first-half item: #{Quotient.member?(merged, hd(first_half))}")
IO.puts("Merged contains second-half item: #{Quotient.member?(merged, hd(second_half))}")

Serialization

binary = Quotient.serialize(filter)
{:ok, restored} = Quotient.deserialize(binary)
IO.puts("Round-tripped membership check: #{Quotient.member?(restored, hd(inserted))}")