Data Structures for Big Data

High-scale distributed systems rely on probabilistic data structures to perform cardinality estimation, membership queries, and frequency counting.

1. Core Probabilistic Data Structures

• Bloom Filters:

A space-efficient bit array used to test set membership. Returns no false negatives (if it says "not present", it is definitely not present) but has a configurable rate of false positives (may say "present" when it is not).

• HyperLogLog (HLL):

Estimates the cardinality of unique items (e.g., daily active users) in constant memory space. Counts trailing zeros of hashed values to estimate cardinality with a standard error of < 1%.

• Count-Min Sketch:

A 2D array of counters using multiple hash functions. Estimates the frequency of events (e.g., top-K trending tags) in stream ingest logs using minimal memory.

2. Trade-offs & Space Efficiency

These structures trade absolute accuracy for dramatic space savings, allowing massive datasets to be evaluated entirely in RAM.

3. References & Tech Blogs

• Google Research: HyperLogLog in Practice
• Cloudflare Blog: How Bloom Filters Protect User Passwords