XorFilter Tutorial

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:

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)

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

Basic usage

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:

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

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:

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:

# 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

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