Bloom Filters and
Probabilistic Data Structures

The exactness tax

Exact data structures (hash tables, balanced trees, sorted arrays) guarantee correct answers, but their space and time costs grow linearly — or worse — with data size.

• Storing 1 billion 64-bit keys in a hash set costs ~8 GB of RAM minimum
• Exact distinct count over a stream requires storing every unique element
• Exact set intersection over two billion-element sets requires materialising both

The probabilistic bargain

Components

Think of it as k different hash tables compressed into a single bit array. Each hash function "votes" on whether the element is present. If all k votes say yes, we report membership — but collisions can cause false positives.

Insert(x)

For each hash function h_i (i = 1..k): compute h_i(x) mod m, set that bit to 1.

Query(x)

For each h_i: if any bit is 0 → definitely not in set. If all bits are 1 → probably in set.

Walk-through

m = 16 bits, k = 3 hash functions

Insert "cat": h1=2, h2=7, h3=13
  [0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0]

Insert "dog": h1=4, h2=7, h3=11
  [0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0]

Query "cat":  2,7,13 all=1 → probably yes ✓
Query "fish": h1=2,h2=4,h3=9 → bit 9=0 → no ✓
Query "bird": h1=2,h2=7,h3=11 → all 1
              → FALSE POSITIVE ✗

Probability derivation

After inserting n elements into an m-bit array with k hash functions:

• Probability a specific bit is still 0: (1 - 1/m)kn
• Approximation: e-kn/m
• False positive probability: (1 - e-kn/m)k

FPP ≈ (1 - e^(-kn/m))^k

Practical numbers

The trade-off

• Too few hash functions — high FPP because fewer bits checked
• Too many hash functions — bit array fills up faster, increasing FPP
• Optimal k balances these two effects

Formulas

k_opt = (m/n) × ln(2) ≈ 0.693 × (m/n)

FPP_min = (1/2)^k ≈ (0.6185)^(m/n)

Practical sizing

Given desired false positive rate p and expected elements n:

m = -n × ln(p) / (ln(2))²
k = (m/n) × ln(2)

Problem

Standard Bloom filters do not support deletion — clearing a bit might remove other elements.

Solution: replace bits with counters

Use a small counter per position (typically 4 bits):

• Insert(x) — increment each counter at h_i(x)
• Delete(x) — decrement each counter at h_i(x)
• Query(x) — all counters > 0? → probably in set

Trade-offs

Structure

• Array of buckets, each holding a small number of slots (typically 4)
• Each element → a fingerprint (8–12 bits)
• Two candidate buckets: b1 = hash(x), b2 = b1 XOR hash(fp(x))

Operations

• Insert — place fingerprint in b1 or b2; if both full, evict (cuckoo displacement)
• Lookup — check fingerprint in b1 or b2
• Delete — remove matching fingerprint from b1 or b2

vs Bloom filters

Cache-friendly alternative

Hash each element to a p-bit fingerprint. Split into q-bit quotient (bucket index) and r-bit remainder (stored value). p = q + r.

Key properties

• Cache-friendly — contiguous array, no pointer chasing
• Mergeable — two filters merged in linear time
• Resizable — can be doubled by redistributing remainders
• Deletion — supported with counting variants

Metadata bits per slot

Problem

Count distinct elements in a massive stream. Exact counting requires O(n) space. HyperLogLog: ~12 KB for billions of elements.

Core insight

Hash elements uniformly. The maximum number of leading zeros in any hash tells you roughly log2(n_distinct).

• Longest run of leading zeros = k → estimate 2k distinct elements
• Single observation is noisy — HyperLogLog uses many independent observations

Real-world usage

Algorithm

1. Hash each element to a uniform binary string
2. Use first b bits to select one of m = 2b registers
3. Count leading zeros in remaining bits; store the maximum per register
4. Estimate: E = αm · m² · (Σ 2-R[j])-1

Corrections

• Small range — many registers empty → use linear counting
• Large range — estimate exceeds 2³²/30 → hash collision correction
• HLL++ (Google, 2013) — improved bias correction, sparse representation

Space and accuracy

Structure

2D array of counters: d rows (hash functions) × w columns (width). d independent hash functions, one per row.

Operations

• Update(x, c) — for each row i, increment counters[i][h_i(x)] by c
• Query(x) — return min(counters[i][h_i(x)]) across all rows

Error bounds

• Estimate is always ≥ true count (over-estimates only)
• With probability 1 - δ: error ≤ ε · ||stream||
• Space: w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉

Walk-through

d=3 rows, w=8 columns

Update("cat", 5):
  row 0 col 3 += 5
  row 1 col 7 += 5
  row 2 col 1 += 5

Update("dog", 3):
  row 0 col 5 += 3
  row 1 col 3 += 3
  row 2 col 1 += 3

Query("cat"):
  min(col3=5, col7=5, col1=8) = 5 ✓

Query("dog"):
  min(col5=3, col3=3, col1=8) = 3 ✓

Problem

Estimate similarity of two sets without full comparison. Jaccard similarity: J(A,B) = |A∩B| / |A∪B|

Algorithm

1. Choose k independent hash functions
2. For each set, compute the minimum hash value under each function
3. Fraction of matching minimums estimates Jaccard similarity

Pr[min(h(A)) = min(h(B))] = J(A, B)

Locality-Sensitive Hashing (LSH)

Combine MinHash signatures into bands for fast approximate nearest-neighbour search:

• Divide signature into b bands of r rows
• Items are candidates if they agree in all rows of at least one band
• Tune b and r to control the S-curve threshold

Applications

Structure

• Level 0 — sorted linked list of all elements
• Level 1+ — each element promoted with probability p (typically 1/2)
• Search starts at the top level, drops down when overshooting

Expected complexity

Why probabilistic?

Balance depends on coin flips during insertion, not deterministic rebalancing. In expectation, levels and search path length are both O(log n).

Real-world usage

Problem

Select k items uniformly at random from a stream of unknown length n, using only O(k) memory.

Algorithm (Vitter's Algorithm R)

reservoir = first k items from stream

for i = k+1 to n:
    j = random integer in [1, i]
    if j <= k:
        reservoir[j] = stream[i]

Each element ends up in the reservoir with probability k/n.

Variants

Applications

• Sampling log lines for analysis without storing the full stream
• A/B test random assignment from an unbounded user stream
• Random row selection from a database table scan

Choosing the right structure

Common pitfalls

Key takeaways

• Probabilistic structures trade bounded, tuneable error for dramatic space and time savings
• Bloom filters remain the workhorse for membership queries — simple, fast, well-analysed
• HyperLogLog is the standard for cardinality estimation in databases and streaming
• Count-Min Sketch is the go-to for frequency estimation in streaming and network monitoring
• Cuckoo filters improve on Bloom filters when deletion is needed or FPP < 3%
• MinHash enables similarity estimation at scale for deduplication and recommendation
• Skip lists prove randomisation can replace complex balancing logic
• Always size structures based on expected volume and acceptable error rate

Recommended reading