# Quotient Filter Tutorial

```elixir
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:

```mermaid
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)

```elixir
{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:

```elixir
alias ExDataSketch.Quotient

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

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

## Safe deletion

```elixir
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

```elixir
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

```elixir
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`:

```elixir
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

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

## See also

* `ExDataSketch.Quotient` module documentation -- full API reference and
  the QOT1 binary layout.
* `ExDataSketch.Cuckoo` -- also supports deletion but not merge, and
  sizes by item capacity rather than bit widths; see
  `livebooks/sketches/cuckoo.livemd`.
* `ExDataSketch.CQF` -- the same quotient-filter data structure extended
  with approximate per-item counting; see `livebooks/sketches/cqf.livemd`.