api: YAML JSON TOON Database
version: 1.0.0
format: yaml
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: 2
  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 × 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.