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
CC0 — public domain

JSON11,249 B
YAML7,698 B · −32%
TOON6,555 B · −42%

Probabilistic data structures for membership, counting and similarity: Bloom, counting Bloom and cuckoo filters, HyperLogLog, Count-Min Sketch and MinHash, each with space use, error behavior, operations, strengths, weaknesses and uses.

Use it when

You need approximate membership, cardinality or frequency with small memory.
You are choosing between a Bloom and a cuckoo filter.

Watch out for

Bloom filters allow false positives but not false negatives; plain Bloom filters do not support deletion.
Accuracy depends on how the structure is sized relative to the expected number of items.

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)

Fields

The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.

Section	Field	Type	Example
structures	`name`	string	Bloom Filter
structures	`type`	string	Membership
structures	`space_usage`	string	m bits for m-bit array
structures	`false_positive_rate`	string	~ (1 - e^{-kn/m})^k where k = hash count, n = e…
structures	`operations`	array	[2 items]
structures	`strengths`	array	[4 items]
structures	`weaknesses`	array	[3 items]
structures	`use_cases`	array	[4 items]
structures	`notes`	string	Optimal hash count k = (m/n) * ln(2). A 10-bit-…
structures	`relative_error`	string	~ 1.04/√m (e.g., 1.5KB → ~2% error for billions)

Fetch the same bytes

The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.

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 →