Probabilistic Data Structures: Bloom Filters & Beyond

Probabilistic data structures for approximate set membership, counting, and cardinality estimation: Bloom filters, Count-Min Sketch, HyperLogLog, and Cuckoo filters.

Data Structures
6 entries
1 sections
CC0 — public domain

The data

Structures

Name	Type	Space usage	False positive rate	Operations	Strengths	Weaknesses	Use cases	Notes	Relative error
Bloom Filter	Membership	m bits for m-bit array	~ (1 - e^{-kn/m})^k where k = hash count, n = elements, m = bits	add possibly_contains	No false negatives Constant-time add/query Very memory efficient No deletion needed for many use cases	Cannot remove elements (counting BF solves this) False positives possible No way to list stored elements	Cache busting (avoid cache misses for non-existent keys) Web crawler URL deduplication Spam email filtering Database query optimization (bloom filter indexes)	Optimal hash count k = (m/n) * ln(2). A 10-bit-per-element filter has ~1% false positive rate.	null
Counting Bloom Filter	Membership with Deletion	m × d bits (d = counter width, typically 4 bits)	Same as standard Bloom Filter	add remove possibly_contains	Supports deletion All base Bloom Filter advantages	4-5x more memory than standard Bloom Counter overflow risk with small counters	Streaming data with deletions Cache with TTL-based eviction Dynamic sets where removals needed	Use 4-bit counters (max 15 increments) to balance memory and overflow risk. Larger d for high-frequency items.	null
Cuckoo Filter	Membership	~ 1.17 bytes per element (for 3% FPR, β = 95% load)	Configurable (typically 1-5%)	add remove contains	Supports deletion natively Better space efficiency than Bloom for low FPR Higher load factor (~95%)	Insertion may fail (relocation limit) More complex implementation Relocation chains on insertion	Database query acceleration Network packet deduplication Distributed systems membership	Uses cuckoo hashing with two hash functions. When bucket full, existing item is kicked to alternate location.	null
HyperLogLog	Cardinality Estimation	~ 1.5 KB for 2^14 registers (standard), error ~ 1.04/√m	null	add count merge	Extremely memory efficient Supports union/merge of independent HLLs Well-understood error bounds	Cannot estimate set intersections directly Inaccurate for very small cardinalities (bias correction needed) Single-set cardinality only	Unique visitor counting Distinct IP addresses in network traffic Reach and frequency estimation Big data analytics	Presto, Redshift, BigQuery, and Redis all implement HyperLogLog natively. Practical limit: trillions of distinct values.	~ 1.04/√m (e.g., 1.5KB → ~2% error for billions)
Count-Min Sketch	Frequency Estimation	d × w counters (d = depth, w = width). Typically d=5, w = 2/ε	null	add estimate_count	Very space efficient for frequency estimation Handles heavy hitters (frequent items) well Mergeable across distributed nodes	Always overestimates (never underestimates) Cannot remove elements Point queries less accurate for low-frequency items	Heavy hitters detection (network traffic) Frequency estimation in streaming data Trending topics/items Query optimization in databases	Used by Apache DataSketches, Redis (top-k), and network monitoring tools. Set d = ceil(ln(1/δ)), w = ceil(2/ε).	Overestimates frequency with probability δ for error bound ε
MinHash	Similarity Estimation	k × 64 bits (k = number of hash functions, typically 128-256)	null	add_document estimate_similarity find_near_duplicates	Fast similarity estimation for large document sets Locality-sensitive hashing variant (LSH) Supports union/intersection estimation	Only estimates Jaccard similarity Requires many hash functions for accuracy Not suitable for exact matching	Near-duplicate document detection Recommendation systems (similar users/items) Large-scale clustering Plagiarism detection	Foundation for many LSH (Locality-Sensitive Hashing) schemes. Google, Amazon, and Netflix use variants for dedup and recommendations.	~ 1/√k for Jaccard similarity (e.g., k=256 → ~6% error)

Fetch the same bytes

The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.

curl "https://yjtoon.com/api/dataset/bloom-filters-probabilistic?format=toon"

const res = await fetch(
  "https://yjtoon.com/static-data/dataset/bloom-filters-probabilistic.toon"
);
const toon = await res.text();

Rate limit: 120 requests per minute per IP, no key and no signup. API reference →

Probabilistic Data Structures: Bloom Filters & Beyond

The data

Structures

Fetch the same bytes

Topics