api: YAML JSON TOON Database version: 1.0.0 format: toon dataset: id: 2328 slug: bloom-filters-probabilistic title: "Probabilistic Data Structures: Bloom Filters & Beyond" description: "Probabilistic data structures for approximate set membership, counting, and cardinality estimation: Bloom filters, Count-Min Sketch, HyperLogLog, and Cuckoo filters." summary: "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_when[2]: "You need approximate membership, cardinality or frequency with small memory.",You are choosing between a Bloom and a cuckoo filter. caveats[2]: 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. related[4]: hash-tables,string-algorithms,complexity-analysis,nosql-databases-overview entry_count: 6 fields[10]{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)" category: Data Structures category_slug: data-structures tags: "bloom-filter,probabilistic,data-structures,hyperloglog,cuckoo-filter,count-min-sketch" view_count: 42 created_at: 1777673262 updated_at: 1777673262 data: structures[6]: - name: Bloom Filter type: Membership space_usage: m bits for m-bit array false_positive_rate: "~ (1 - e^{-kn/m})^k where k = hash count, n = elements, m = bits" operations[2]: add,possibly_contains strengths[4]: No false negatives,Constant-time add/query,Very memory efficient,No deletion needed for many use cases weaknesses[3]: Cannot remove elements (counting BF solves this),False positives possible,No way to list stored elements use_cases[4]: Cache busting (avoid cache misses for non-existent keys),Web crawler URL deduplication,Spam email filtering,Database query optimization (bloom filter indexes) notes: Optimal hash count k = (m/n) * ln(2). A 10-bit-per-element filter has ~1% false positive rate. - name: Counting Bloom Filter type: Membership with Deletion space_usage: "m × d bits (d = counter width, typically 4 bits)" false_positive_rate: Same as standard Bloom Filter operations[3]: add,remove,possibly_contains strengths[2]: Supports deletion,All base Bloom Filter advantages weaknesses[2]: 4-5x more memory than standard Bloom,Counter overflow risk with small counters use_cases[3]: Streaming data with deletions,Cache with TTL-based eviction,Dynamic sets where removals needed notes: Use 4-bit counters (max 15 increments) to balance memory and overflow risk. Larger d for high-frequency items. - name: Cuckoo Filter type: Membership space_usage: "~ 1.17 bytes per element (for 3% FPR, β = 95% load)" false_positive_rate: Configurable (typically 1-5%) operations[3]: add,remove,contains strengths[3]: Supports deletion natively,Better space efficiency than Bloom for low FPR,Higher load factor (~95%) weaknesses[3]: Insertion may fail (relocation limit),More complex implementation,Relocation chains on insertion use_cases[3]: Database query acceleration,Network packet deduplication,Distributed systems membership notes: "Uses cuckoo hashing with two hash functions. When bucket full, existing item is kicked to alternate location." - name: HyperLogLog type: Cardinality Estimation space_usage: "~ 1.5 KB for 2^14 registers (standard), error ~ 1.04/√m" relative_error: "~ 1.04/√m (e.g., 1.5KB → ~2% error for billions)" operations[3]: add,count,merge strengths[3]: Extremely memory efficient,Supports union/merge of independent HLLs,Well-understood error bounds weaknesses[3]: Cannot estimate set intersections directly,Inaccurate for very small cardinalities (bias correction needed),Single-set cardinality only use_cases[4]: Unique visitor counting,Distinct IP addresses in network traffic,Reach and frequency estimation,Big data analytics notes: "Presto, Redshift, BigQuery, and Redis all implement HyperLogLog natively. Practical limit: trillions of distinct values." - name: Count-Min Sketch type: Frequency Estimation space_usage: "d × w counters (d = depth, w = width). Typically d=5, w = 2/ε" relative_error: Overestimates frequency with probability δ for error bound ε operations[2]: add,estimate_count strengths[3]: Very space efficient for frequency estimation,Handles heavy hitters (frequent items) well,Mergeable across distributed nodes weaknesses[3]: Always overestimates (never underestimates),Cannot remove elements,Point queries less accurate for low-frequency items use_cases[4]: Heavy hitters detection (network traffic),Frequency estimation in streaming data,Trending topics/items,Query optimization in databases notes: "Used by Apache DataSketches, Redis (top-k), and network monitoring tools. Set d = ceil(ln(1/δ)), w = ceil(2/ε)." - name: MinHash type: Similarity Estimation space_usage: "k × 64 bits (k = number of hash functions, typically 128-256)" relative_error: "~ 1/√k for Jaccard similarity (e.g., k=256 → ~6% error)" operations[3]: add_document,estimate_similarity,find_near_duplicates strengths[3]: Fast similarity estimation for large document sets,Locality-sensitive hashing variant (LSH),Supports union/intersection estimation weaknesses[3]: Only estimates Jaccard similarity,Requires many hash functions for accuracy,Not suitable for exact matching use_cases[4]: Near-duplicate document detection,Recommendation systems (similar users/items),Large-scale clustering,Plagiarism detection notes: "Foundation for many LSH (Locality-Sensitive Hashing) schemes. Google, Amazon, and Netflix use variants for dedup and recommendations."