Bloom Filter Tutorial

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

Introduction

ExDataSketch.Bloom is a bit array plus k independent hash functions. Inserting an item sets k bits (one per hash function); checking an item passes if all k of its bits are set. Bits are shared across every item, so a bit being set never proves any specific item set it -- which is exactly why membership checks can occasionally lie in one direction (say "yes" for an item never inserted) but never the other (say "no" for one that was):

flowchart LR
    A[item] --> B["k hash functions"]
    B --> C{"all k bits\nset?"}
    C -->|no| D["definitely not\npresent"]
    C -->|yes| E["probably present\n(maybe a false positive)"]

No false negatives (if it says "no," the item was definitely never inserted) but a tunable rate of false positives (if it says "yes," it's probably right, but might be wrong). It's the simplest and most widely used of the membership filters here.

Use it for: deduplication, "is this URL on the blocklist," "should I even bother checking the database for this key" -- any cheap first-pass membership check where an occasional false "yes" is tolerable (worst case, you do one unnecessary real lookup) but a false "no" would silently drop something real.

Don't use it for: anywhere a false positive is unacceptable (use an exact MapSet/database lookup, or see ExDataSketch.Cuckoo if you also need deletion); anywhere you need to remove items later -- Bloom has no delete/2 at all, since clearing a bit could un-set it for other items that share it; iterating or listing what's stored -- a Bloom filter can only answer "is this specific item probably in here," never "what's in here."

What it buys you: each item costs a fixed number of bits, independent of the item's own size. At the default false_positive_rate: 0.01 (1%), that's about 9.6 bits/item -- 500,000 URLs (used throughout this tutorial) cost a fixed ~585 KB, whichever way you tune it that's dramatically less than storing the URLs themselves:

Approach	Memory (500,000 URLs)	Answer
Exact set (raw URL strings)	15+ MB (grows with item size)	Exact
`ExDataSketch.Bloom` (1% FPR)	~585 KB, fixed bits/item	Maybe (1% false positive rate)

Sample data (cached locally)

500,000 URLs we've "crawled" (to insert), and 500,000 different URLs we haven't (to test the false-positive rate against).

{inserted, novel} = ExDataSketch.SampleData.bloom_urls()
IO.puts("#{length(inserted)} inserted URLs, #{length(novel)} novel URLs to test against")

Basic usage

alias ExDataSketch.Bloom

filter = Bloom.new(capacity: 500_000, false_positive_rate: 0.01)
filter = Bloom.put(filter, "https://example.com/page/1")

Bloom.member?(filter, "https://example.com/page/1")

put_many/2 is far more efficient than looping put/2 for a batch:

filter = Bloom.new(capacity: 500_000, false_positive_rate: 0.01) |> Bloom.put_many(inserted)

IO.puts("Filter size: #{Bloom.size_bytes(filter)} bytes for #{length(inserted)} items")

No false negatives, measured false-positive rate

Every inserted item must test as a member (no false negatives, ever). Every novel item might incorrectly test as a member (false positive) -- measure the actual rate against the configured target:

all_inserted_found? = Enum.all?(inserted, &Bloom.member?(filter, &1))
IO.puts("All inserted URLs found: #{all_inserted_found?}")

false_positives = Enum.count(novel, &Bloom.member?(filter, &1))
observed_fpr = false_positives / length(novel)

IO.puts("False positives: #{false_positives} / #{length(novel)} (#{Float.round(observed_fpr * 100, 3)}%)")
IO.puts("Configured target: #{filter.opts[:false_positive_rate] * 100}%")

Sizing: capacity and false_positive_rate

Both :capacity and :false_positive_rate feed directly into the derived bit-array size -- lower FPR or higher capacity means more memory:

for fpr <- [0.1, 0.01, 0.001] do
  f = Bloom.new(capacity: 500_000, false_positive_rate: fpr) |> Bloom.put_many(inserted)
  observed = Enum.count(Enum.take(novel, 50_000), &Bloom.member?(f, &1)) / 50_000

  IO.puts(
    "target=#{fpr * 100}% (#{f.opts[:bit_count]} bits, #{Bloom.size_bytes(f)} bytes): " <>
      "observed=#{Float.round(observed * 100, 3)}%"
  )
end

Merging

Bloom merge is a bitwise OR -- both filters must share identical bit_count/hash_count/seed (i.e. identical :capacity/ :false_positive_rate/:seed at construction):

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

worker_a = Bloom.new(capacity: 500_000, false_positive_rate: 0.01) |> Bloom.put_many(first_half)
worker_b = Bloom.new(capacity: 500_000, false_positive_rate: 0.01) |> Bloom.put_many(second_half)

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

Serialization

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

What Bloom can't do

Bloom filters can't be shrunk or have individual items removed (setting bits back to 0 could un-set a bit another item also depends on), and can't tell you how many distinct items were inserted, or which items those were. If you need deletion, see livebooks/sketches/cuckoo.livemd or livebooks/sketches/quotient.livemd; if you need approximate counting per item, see livebooks/sketches/cqf.livemd.