Probabilistic Data Structures for Big Data

When operating at petabyte scale, exact data structures (like HashMaps and HashSets) consume hundreds of gigabytes of RAM. Probabilistic data structures trade a tiny, bounded margin of error for constant $O(1)$ memory efficiency.

1. Bloom Filter (Set Membership)

• Goal: Answer *"Has this URL been crawled?"* or *"Does this username exist?"* with zero false negatives.
• Mechanism: A bit array of size $m$ and $k$ independent hash functions.
• Guarantees:
• If it returns False: The element is definitely NOT in the set.
• If it returns True: The element is probably in the set (small false positive rate $p$).
• Storage Savings: Checks 1 Billion URLs using only ~1.2 GB of RAM instead of 64 GB for a HashSet.

2. HyperLogLog (Cardinality Counting)

• Goal: Count Unique Daily Active Users (DAU) or distinct IP addresses.
• Mechanism: Hashes incoming values, counts the number of leading zeros in the binary representation. The probability of seeing $k$ leading zeros is $2^{-k}$.
• Scale: HyperLogLog can estimate the cardinality of billions of items with an error rate under 1% using only 1.5 KB of memory!

3. Count-Min Sketch (Frequency Estimation)

• Goal: Find the most frequent items ("Heavy Hitters" / Top-$K$ trending hashtags) in a streaming network.
• Uses a 2D array of counters with depth $d$ and width $w$. Increments counters on write, returns the minimum value across hashes on query.

Key Architecture Trade-Offs & Decision Matrix