{ "api": "YAML JSON TOON Database", "version": "1.0.0", "format": "json", "dataset": { "id": 366, "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.", "category": "Data Structures", "category_slug": "data-structures", "tags": "bloom-filter,probabilistic,data-structures,hyperloglog,cuckoo-filter,count-min-sketch", "view_count": 1, "created_at": 1781275786, "updated_at": 1781275786 }, "data": { "structures": [ { "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": [ "add", "possibly_contains" ], "strengths": [ "No false negatives", "Constant-time add\/query", "Very memory efficient", "No deletion needed for many use cases" ], "weaknesses": [ "Cannot remove elements (counting BF solves this)", "False positives possible", "No way to list stored elements" ], "use_cases": [ "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 \u00d7 d bits (d = counter width, typically 4 bits)", "false_positive_rate": "Same as standard Bloom Filter", "operations": [ "add", "remove", "possibly_contains" ], "strengths": [ "Supports deletion", "All base Bloom Filter advantages" ], "weaknesses": [ "4-5x more memory than standard Bloom", "Counter overflow risk with small counters" ], "use_cases": [ "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, \u03b2 = 95% load)", "false_positive_rate": "Configurable (typically 1-5%)", "operations": [ "add", "remove", "contains" ], "strengths": [ "Supports deletion natively", "Better space efficiency than Bloom for low FPR", "Higher load factor (~95%)" ], "weaknesses": [ "Insertion may fail (relocation limit)", "More complex implementation", "Relocation chains on insertion" ], "use_cases": [ "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\/\u221am", "relative_error": "~ 1.04\/\u221am (e.g., 1.5KB \u2192 ~2% error for billions)", "operations": [ "add", "count", "merge" ], "strengths": [ "Extremely memory efficient", "Supports union\/merge of independent HLLs", "Well-understood error bounds" ], "weaknesses": [ "Cannot estimate set intersections directly", "Inaccurate for very small cardinalities (bias correction needed)", "Single-set cardinality only" ], "use_cases": [ "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 \u00d7 w counters (d = depth, w = width). Typically d=5, w = 2\/\u03b5", "relative_error": "Overestimates frequency with probability \u03b4 for error bound \u03b5", "operations": [ "add", "estimate_count" ], "strengths": [ "Very space efficient for frequency estimation", "Handles heavy hitters (frequent items) well", "Mergeable across distributed nodes" ], "weaknesses": [ "Always overestimates (never underestimates)", "Cannot remove elements", "Point queries less accurate for low-frequency items" ], "use_cases": [ "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\/\u03b4)), w = ceil(2\/\u03b5)." }, { "name": "MinHash", "type": "Similarity Estimation", "space_usage": "k \u00d7 64 bits (k = number of hash functions, typically 128-256)", "relative_error": "~ 1\/\u221ak for Jaccard similarity (e.g., k=256 \u2192 ~6% error)", "operations": [ "add_document", "estimate_similarity", "find_near_duplicates" ], "strengths": [ "Fast similarity estimation for large document sets", "Locality-sensitive hashing variant (LSH)", "Supports union\/intersection estimation" ], "weaknesses": [ "Only estimates Jaccard similarity", "Requires many hash functions for accuracy", "Not suitable for exact matching" ], "use_cases": [ "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." } ] } }