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:
        [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."