#📝 Note: Bloom Filters

#Overview

A Bloom Filter is a space-efficient, probabilistic data structure used to test whether an element is a member of a set. It is designed to quickly verify membership with minimal memory usage, making it ideal for distributed systems handling large-scale data.

#Core Idea

• Membership Test: A Bloom filter can produce two results:
  • "Definitely not in set" (False negatives are impossible).
  • "Probably in set" (False positives are possible).
• Structure: It consists of a bit array of size $m$ initialized to all 0s, and $k$ independent hash functions.
• Operations:
  • Insertion: Run the element through the $k$ hash functions to get $k$ array positions. Set the bits at those positions to 1.
  • Lookup: Run the element through the $k$ hash functions. If any of the bits at these positions is 0, the element is definitely not in the set. If all bits are 1, the element is probably in the set.

Element: "url1" ──► Hash1(url1) % m = 2 ──► Set bit 2 to 1
               ──► Hash2(url1) % m = 7 ──► Set bit 7 to 1

Bit Array:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │
└───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5   6   7

#Mathematical Foundation

To design a Bloom Filter, we must calculate the optimum array size $m$ and number of hash functions $k$ for a target capacity $n$ (number of elements) and a tolerable false positive probability $p$.

1. Optimal Number of Hash Functions ($k$):
   $$k = \frac{m}{n} \ln 2 \approx 0.7 \times \frac{m}{n}$$

2. Optimal Bit Array Size ($m$):
   $$m = - \frac{n \ln p}{(\ln 2)^2} \approx -1.44 \times n \log_2 p$$

Example: For $n = 1\text{ Billion}$ elements and a false positive rate $p = 1%$, we need:

• $m \approx 9.56\text{ Billion bits} \approx 1.2\text{ GB}$ of memory.
• $k \approx 7$ hash functions.
• Compare this with storing 1 Billion 100-character URLs (~100 GB)! A Bloom Filter saves ~99% of the memory.

#Why Use Bloom Filters?

• URL Deduplication: Prevent crawlers from visiting the same page twice.
• Database Query Reduction: Databases like Cassandra, RocksDB, and HBase use them to check if a row key exists in an SSTable before performing expensive disk I/O.
• Content Recommendation: Keep track of read/viewed history to avoid recommending duplicate posts.
• Cache Filtering: Prevent caching one-hit wonders (items only accessed once) in a CDN.

#Trade-offs & Limitations

• Pros:
  • Space Efficiency: Very small memory footprint relative to the set size.
  • Constant Time O(k): Insertions and lookups take $O(k)$ time, independent of the number of items in the set.
  • Privacy: Does not store the actual values of items, only their hash signatures.
• Cons:
  • False Positives: An item may be reported as "present" when it was never added.
  • No Deletion: You cannot delete an item because setting a bit back to 0 might accidentally delete other items sharing that bit position.
    • Mitigation: Counting Bloom Filters use an array of counters instead of bits to support deletion, but require 3–4x more memory.
  • No Dynamic Resizing: The filter size must be declared upfront. If the number of elements $n$ exceeds the initial design, the false positive rate degrades rapidly.
    • Mitigation: Scalable Bloom Filters chain multiple Bloom Filters of increasing size dynamically.