api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  id: 44
  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: 0
  created_at: 1777673262
  updated_at: 1777673262
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 × 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, β = 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/√m"
      relative_error: "~ 1.04/√m (e.g., 1.5KB → ~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 × w counters (d = depth, w = width). Typically d=5, w = 2/ε"
      relative_error: "Overestimates frequency with probability δ for error bound ε"
      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/δ)), 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:
        - "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."