Phase 4Intermediate5 of 12 in Bloom Filters

Variants and Alternatives

Scalable Bloom filters for unknown sizes, Counting Bloom and Cuckoo filters for deletion, blocked and partitioned layouts for CPU speed, Quotient, Xor and Ribbon filters, and a decision guide against HashSet, HyperLogLog and Count-Min Sketch.

The classic Bloom filter has three limits: it needs a known capacity, it can't delete, and each lookup touches k random cache lines. Each variant here removes one limit at a cost.

The phase ends with a decision guide, because choosing the right structure matters more than tuning the wrong one.

0/6 · 0%

6 topics ~49 min 10 code blocks & diagrams

Start with the first topic

4.1

Scalable Bloom Filters: Growing Without Knowing n

A scalable Bloom filter chains sub-filters: when the current one reaches capacity, a new, larger one is added with a tighter error rate. Inserts go to the newest; lookups check all. With geometric growth (s) and error tightening (r), total FPR stays below P0/(1 − r).

9 min 1 diagram 1 code practice

4.2

Counting Bloom Filters: Deletion with Counters

Clearing a bit on delete can erase another item's bit and create false negatives. A counting Bloom filter replaces each bit with a small counter (typically 4 bits): insert increments, delete decrements, and lookup checks counters are non-zero. It supports deletion at about 4× the memory.

9 min 2 code practice

4.3

Cuckoo Filters: Fingerprints, Buckets, and Deletion

A cuckoo filter stores short fingerprints of items in a table of buckets (typically 4 slots each); each item has two candidate buckets and insertion evicts and relocates existing fingerprints when both are full. It supports deletion, reaches ~95% occupancy, and uses less space than a Bloom filter when the target error is below about 3%.

9 min 2 code practice

4.4

Blocked and Partitioned Bloom Filters: Cache-Friendly Layouts

A standard lookup touches k random cache lines. A blocked Bloom filter hashes each item to one 512-bit block (a CPU cache line) and sets all k bits inside it, so a lookup costs one cache miss, at a slightly higher false-positive rate. Partitioned filters give each hash its own slice of the array.

7 min 1 diagram practice

4.5

Quotient, Xor, Binary Fuse, and Ribbon Filters

Quotient filters store fingerprints in a compact open-addressed table (deletable, resizable, mergeable, cache-friendly). Xor and binary fuse filters (static sets) use ~1.23 and ~1.13 × log2(1/ε) bits per item with three lookups. Ribbon filters (RocksDB) give similar savings for static SST files.

7 min 1 code practice

4.6

Choosing: Bloom vs HashSet vs HyperLogLog vs Count-Min

Use a HashSet when you need exact answers, the values themselves, or the data fits in memory; a Bloom-family filter when the set is huge, memory is tight and false positives are acceptable; HyperLogLog for distinct counts; Count-Min Sketch for frequencies. Never confuse membership, cardinality and frequency.

8 min 1 diagram 1 code practice