Probabilistic data structures

01Probabilistic data structures: definition and error models

A probabilistic data structure uses randomization, often through hashing, to obtain useful space or performance tradeoffs. The broader category also includes randomized exact structures, such as skip lists; probabilistic does not always mean an approximate answer. This chapter focuses on compact approximate summaries with stated error models. A Bloom filter approximates set membership, HyperLogLog estimates the number of distinct items, and Count-Min Sketch estimates how often a supplied item occurs. These summaries save memory or work by discarding information. The engineering task is to know which mistakes are possible and place each summary where those mistakes are acceptable.

Use approximate structures where their error model is acceptable, using exact records and checks for decisions that cannot safely be reversed. The worked crawler calculation assumes one million stored normalized URLs and 100,000 membership checks, of which 80% concern absent URLs. These inputs are illustrative assumptions. The exact URL database remains responsible for unique discovery and scheduling.

An in-memory hash set can answer membership exactly, but storing every full URL and its indexing overhead may consume too much memory. A database lookup for every candidate can also be expensive. A Bloom filter can cheaply rule out many absent candidates. It does not store the URLs themselves, prove that a page was fetched successfully, or replace the exact claim that prevents two workers from scheduling the same URL.

02Bloom filter: bit array, hashes, and false positives

A Bloom filter is a bit array plus several hash functions. A hash function maps an item to a position in that array. To insert a URL, set its positions to one. To test a URL, inspect those positions: any zero proves it was not inserted into this filter; all ones mean only “possibly present.”

Use a tiny sixteen-bit filter and two illustrative hashes. Initially every bit is zero.

C is a false positive created by shared bits. A and B remain discoverable because insertion never clears their positions. “No false negatives” relies on correct insertion, intact state, consistent hashing, and the filter representing the set being queried. It is not a promise about a stale or partially rebuilt copy of the database.

03Bloom filter with an exact membership database

With the assumed 1% false-positive rate, 80,000 absent queries cause about 800 false positives. The 20,000 present queries also require exact verification. Expected membership reads therefore fall from 100,000 to about 20,800, saving about 79,200. These figures concern preliminary reads, not all database operations: durable inserts and claim checks remain.

If a URL is in the database but missing from the filter, the filter can wrongly report it absent. An atomic database claim can still prevent duplicate scheduling. A design that trusts the filter’s negative result without that check cannot. Record which data the filter covers and what changes a rebuild includes.

04Bloom filter sizing: bits, hashes, and false-positive rate

Sizing starts with how many distinct URLs the filter must cover and how many unnecessary exact lookups are acceptable. From that expected population and target false-positive rate, choose the number of stored bits and hash positions. The formulas below quantify the memory-versus-error tradeoff under their hashing assumptions.

For an idealized Bloom filter with good hashing, expected false-positive probability is approximately p ≈ (1 − e^(−kn/m))^k, where m is bits, n inserted distinct items, and k hash positions per item. Here e is approximately 2.718, and ln denotes the natural logarithm. Near the optimal hash count, useful sizing formulas are m ≈ −n ln(p)/(ln 2)^2 and k ≈ (m/n) ln 2.

For n = 1,000,000 and p = 0.01, this gives about 9.59 million bits, or 1.20 MB using decimal units, with approximately seven hashes. That excludes object headers, alignment, and implementation overhead. It is roughly 9.6 bits per stored URL, regardless of the URL’s length, because the filter does not retain the original text.

Exceeding the planned population sets more bits and raises the false-positive rate. It does not suddenly start forgetting inserted items, but its ability to reject absent queries deteriorates. Capacity and hash quality must be monitored. A smaller error target costs memory and hash work; choose it using the database work saved, not a habit of demanding the smallest possible percentage.

05Bloom filter deletion, rebuilds, and coverage

For an append-only visited-URL set, an append-only filter rebuilt periodically is simpler. A rebuild must cover a consistent source snapshot plus changes made during construction, or queries must use a safe bypass while coverage is incomplete. On a crash or corrupt filter, fall back to the exact store until a valid filter is available. A performance accelerator should fail into additional work rather than permanent omissions.

If visited URLs expire, define which time period each filter covers or use a supported deletion method. Rotating filters changes the set that membership answers describe. Bitwise OR combines compatible filters into a union, but representing more URLs raises the false-positive rate.

Concurrency is another correctness assumption. Two unsynchronized read-modify-write updates to the same bit-array word can overwrite each other even when each worker only intends to set bits. Use the implementation's supported atomic updates or synchronization. The same care applies to counting-filter increments and decrements; an accelerator implemented with lost updates can violate its advertised error direction.

06HyperLogLog and Count-Min Sketch

Distinct-count estimation is a separate query from membership. A HyperLogLog sketch estimates how many distinct URLs occurred. Each register is a small stored number. Some leading hash bits select a register; in the remaining bits, count leading zeros plus one and retain that register’s largest observed count. In a toy four-register setup, 01 | 0001... selects the register numbered 1 and contributes 4. A later 01 | 01... contributes 2, so the register stays 4. Long zero runs become more likely as more distinct items arrive. HyperLogLog combines all registers using a calibrated estimator, rather than treating one rare hash as an exact count. Repeating the same URL does not represent another distinct item. It cannot answer whether C was present or list the discovered URLs.

Different randomized hash assignments can produce different estimates for the same true distinct count. Relative standard error describes the statistical spread of those estimates relative to that count. More registers reduce that spread at the cost of more memory.

A Count-Min Sketch answers approximate frequency questions, such as how often host H appeared. It uses several rows of counters, each with its own hash selecting one column. Each occurrence increments one counter per row; querying that key returns the minimum of those same counters. In an insert-only stream with nonnegative increments, collisions can overestimate a frequency but do not make that estimate smaller than the actual count. If H occurred twenty times and its counters are 27, 23 and 22, the estimate is 22. Hash collisions explain the extra two; the sketch does not identify the colliding hosts.

For Count-Min, width is the number of counters in each row and depth is the number of independently hashed rows. More columns reduce collisions; additional rows make it less likely that every row badly overestimates the same key. The error target determines these two memory costs.

The standard Count-Min dimensions make the tradeoff concrete: choose width ceil(e / epsilon) and depth ceil(ln(1 / delta)). For a fixed queried key in a nonnegative stream, suitable independent hashes give an estimate between its true count f and f + epsilon * N with probability at least 1 - delta, where N is the sum of all increments across the stream. epsilon sets the allowed additive error as a fraction of N; delta is the maximum failure probability for that bound. ceil(x) is the smallest integer greater than or equal to x, so an integer stays unchanged. ln is the natural logarithm, and e ≈ 2.71828; use the unrounded constant when calculating the width. With epsilon = 0.001, delta = 0.01 and N = 1,000,000, width 2,719 and depth 5 use 13,595 counters. The promised additive error can still be 1,000, which is large for a host seen only twenty times. This is not a simultaneous guarantee for every adaptively chosen key; counter overflow or unsupported signed updates also invalidate the simple bound.

07Bloom filter, HyperLogLog, and Count-Min comparison

Count-Min’s additive error is related to total stream volume under its stated probabilistic bounds, so a small relative error for the whole stream can be large for a rare host. Finding heavy hosts also needs candidate tracking. Compatible sketches can merge—HyperLogLog by register maxima and Count-Min by counter sums—but parameters, hash conventions, and event semantics must match.

In an interview I would say: “The Bloom filter can avoid a preliminary database read when a URL is definitely absent from the covered set. The database’s unique insert still prevents two workers from scheduling the same URL. HyperLogLog drives approximate distinct-count dashboards, and Count-Min helps identify frequency candidates. None is the authoritative record for a decision where an approximate answer can silently lose work.”

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.