# XorFilter Tutorial

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

## Introduction

`ExDataSketch.XorFilter` answers the same "have I seen this" question
as `ExDataSketch.Bloom`, for **static** data known up front. Building
it runs a peeling algorithm over the whole input at once (repeatedly
finding items whose 3 hash positions currently have only one free
slot, assigning that slot, and removing the item) to arrive at a
fingerprint table where every stored item's fingerprint equals the XOR
of its 3 slots -- which is what makes a query just 3 memory reads and
an XOR, no probing or chaining:

```mermaid
flowchart LR
    A[item] --> B["3 hash positions\nh0, h1, h2"]
    B --> C{"fingerprint(item) ==\ntable[h0] XOR table[h1]\nXOR table[h2]?"}
    C -->|yes| D["probably present"]
    C -->|no| E["definitely not present"]
```

Needing the whole input up front for that peeling step is exactly why
there's no `put/2`, `delete/2`, `merge/2`, or even an empty starting
state -- you build it once from a complete collection via `build/2`
and only ever query it after that.

**Use it for:** static or refresh-cycle data -- a blocklist you rebuild
nightly, a compiled dictionary, a fixed allowlist shipped with a
release -- anything built once from a complete collection and queried
many times between refreshes.

**Don't use it for:** anything that changes between refreshes -- there
is no incremental update at all; use `ExDataSketch.Bloom` or
`ExDataSketch.Cuckoo` if items arrive continuously. Also not for
combining two filters -- there's no `merge/2`; rebuild from the
combined item set instead.

**What it buys you:** Xor8 (the default) costs ~9.84 bits/item for a
~0.39% false-positive rate -- close to Bloom's bits/item at 1% FPR, but
noticeably more accurate at essentially the same memory:

| Approach                    | Memory (500,000 domains) | Bits/item | FPR    |
| ------------------------------ | --------------------------- | ----------- | -------- |
| `ExDataSketch.Bloom` (1% FPR) | ~585 KB                      | ~9.6        | 1%       |
| `ExDataSketch.XorFilter` (Xor8) | ~600 KB                     | ~9.84       | ~0.39%   |

## Sample data (cached locally)

```elixir
{blocklist, novel} = ExDataSketch.SampleData.xor_filter_domains()
IO.puts("#{length(blocklist)} blocklisted domains, #{length(novel)} novel (safe) domains")
```

## Basic usage

```elixir
alias ExDataSketch.XorFilter

{:ok, filter} = XorFilter.build(blocklist)

XorFilter.member?(filter, hd(blocklist))
```

`build/2` is the only constructor -- there's no `new/1` to start from and
add to incrementally. It can fail (`{:error, :build_failed}`) in rare
cases with pathological input, though it succeeds virtually always in
practice:

```elixir
case XorFilter.build(blocklist) do
  {:ok, filter} -> IO.puts("Built successfully: #{XorFilter.count(filter)} items")
  {:error, :build_failed} -> IO.puts("Build failed -- try again or check for degenerate input")
end
```

## No false negatives, measured false-positive rate

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

## Xor8 vs Xor16, and vs Bloom at a comparable size

Xor8 (~1/256 theoretical FPR) and Xor16 (~1/65536) trade memory for
accuracy the same way Bloom's `:false_positive_rate` does -- compare
directly against a same-size Bloom filter:

```elixir
alias ExDataSketch.Bloom

{:ok, xor8} = XorFilter.build(blocklist, fingerprint_bits: 8)
{:ok, xor16} = XorFilter.build(blocklist, fingerprint_bits: 16)
bloom = Bloom.new(capacity: 500_000, false_positive_rate: 0.004) |> Bloom.put_many(blocklist)

sample_novel = Enum.take(novel, 50_000)

for {label, size, fpr_check} <- [
      {"Xor8", XorFilter.size_bytes(xor8), fn -> Enum.count(sample_novel, &XorFilter.member?(xor8, &1)) end},
      {"Xor16", XorFilter.size_bytes(xor16), fn -> Enum.count(sample_novel, &XorFilter.member?(xor16, &1)) end},
      {"Bloom (~0.4% target)", Bloom.size_bytes(bloom), fn -> Enum.count(sample_novel, &Bloom.member?(bloom, &1)) end}
    ] do
  fps = fpr_check.()
  IO.puts("#{label}: #{size} bytes, observed FPR=#{Float.round(fps / length(sample_novel) * 100, 4)}%")
end
```

## Rebuilding when the data changes

Since there's no incremental update, refreshing a XorFilter means
rebuilding it from the full, current item set -- a natural fit for a
periodic (nightly, hourly) batch job rather than a live stream:

```elixir
# Simulating "today's blocklist changed slightly":
updated_blocklist = blocklist ++ ["new-malicious-domain.example"]
{:ok, refreshed} = XorFilter.build(updated_blocklist)
IO.puts("Refreshed filter contains the new entry: #{XorFilter.member?(refreshed, "new-malicious-domain.example")}")
```

## Serialization

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

## See also

* `ExDataSketch.XorFilter` module documentation -- full API reference
  and the hypergraph-peeling construction algorithm.
* `ExDataSketch.Bloom` -- mutable and mergeable, for data that changes
  incrementally; see `livebooks/sketches/bloom.livemd`.
* `ExDataSketch.FilterChain` -- XorFilter can be one stage in a chain
  (as a static, precise second-pass filter behind a cheap mutable
  first pass); see `livebooks/sketches/filter_chain.livemd`.