Probabilistic data structures including Bloom filters, HyperLogLog, Count-Min Sketch for space-efficient approximations
Scope: Bloom filters, HyperLogLog, Count-Min Sketch, space-efficient algorithms Lines: ~240 Last Updated: 2025-10-27 Format Version: 1.0 (Atomic)
Activate this skill when:
Traditional data structures: Exact answers, more space
Probabilistic structures: Approximate answers, less space
Example: Set membership
- Hash set: O(n) space, exact
- Bloom filter: O(1) space per element, small false positive ratePurpose: Test set membership with false positives (but no false negatives)
Bloom filter says:
- "Definitely not in set" → 100% accurate
- "Probably in set" → May have false positivesimport hashlib
class BloomFilter:
"""Space-efficient probabilistic set"""
def __init__(self, size=1000, num_hashes=3):
self.size = size
self.num_hashes = num_hashes
self.bits = [False] * size
def _hashes(self, item):
"""Generate k hash values"""
hashes = []
for i in range(self.num_hashes):
# Use different seeds for each hash
hash_input = f"{item}:{i}".encode()
hash_val = int(hashlib.md5(hash_input).hexdigest(), 16)
hashes.append(hash_val % self.size)
return hashes
def add(self, item):
"""Add item to set"""
for hash_val in self._hashes(item):
self.bits[hash_val] = True
def contains(self, item):
"""Check if item might be in set"""
return all(self.bits[h] for h in self._hashes(item))
# Usage
bf = BloomFilter(size=1000, num_hashes=3)
bf.add('apple')
bf.add('banana')
print(bf.contains('apple')) # True (definitely added)
print(bf.contains('cherry')) # False (definitely not added)
print(bf.contains('xyz')) # Maybe False (could be false positive)
# False positive rate depends on size, num_hashes, num_items✅ Cache filtering (check before expensive lookup)
✅ Deduplication (seen this data before?)
✅ Spell checking (is this a valid word?)
✅ Network routers (packet filtering)Example: Cache Filter
class CachedStore:
def __init__(self):
self.cache = {}
self.bloom = BloomFilter(size=10000)
def get(self, key):
# Quick check with Bloom filter
if not self.bloom.contains(key):
# Definitely not in cache
return self.fetch_from_db(key)
# Maybe in cache - check actual cache
if key in self.cache:
return self.cache[key]
else:
# False positive
return self.fetch_from_db(key)
def put(self, key, value):
self.cache[key] = value
self.bloom.add(key)Purpose: Estimate cardinality (count distinct elements) with small memory
Traditional: Store all elements → O(n) space
HyperLogLog: Fixed memory (few KB) → estimates count within 2% errorimport hashlib
import math
class HyperLogLog:
"""Cardinality estimation"""
def __init__(self, precision=14):
self.precision = precision
self.m = 1 << precision # 2^precision buckets
self.registers = [0] * self.m
def _hash(self, item):
"""Hash item to 64-bit value"""
return int(hashlib.md5(str(item).encode()).hexdigest(), 16) & ((1 << 64) - 1)
def add(self, item):
"""Add item"""
h = self._hash(item)
# Use first p bits for bucket index
bucket = h & (self.m - 1)
# Count leading zeros in remaining bits
remaining = h >> self.precision
leading_zeros = self._count_leading_zeros(remaining, 64 - self.precision)
# Update register with maximum
self.registers[bucket] = max(self.registers[bucket], leading_zeros + 1)
def cardinality(self):
"""Estimate cardinality"""
# Harmonic mean of 2^register values
raw_estimate = self._alpha() * (self.m ** 2) / sum(2 ** (-reg) for reg in self.registers)
# Bias correction for small/large cardinalities
if raw_estimate <= 2.5 * self.m:
# Small range correction
zeros = self.registers.count(0)
if zeros != 0:
return self.m * math.log(self.m / zeros)
return int(raw_estimate)
def _alpha(self):
"""Bias correction constant"""
if self.m >= 128:
return 0.7213 / (1 + 1.079 / self.m)
elif self.m >= 64:
return 0.709
elif self.m >= 32:
return 0.697
else:
return 0.673
def _count_leading_zeros(self, value, max_width):
"""Count leading zeros"""
if value == 0:
return max_width
return max_width - value.bit_length()
def merge(self, other):
"""Merge with another HyperLogLog"""
for i in range(self.m):
self.registers[i] = max(self.registers[i], other.registers[i])
# Usage
hll = HyperLogLog()
# Add millions of items
for i in range(1000000):
hll.add(f"user_{i}")
print(f"Estimated unique users: {hll.cardinality()}") # ~1,000,000
# Uses only ~16KB memory!✅ Unique visitors counting (web analytics)
✅ Distinct IP addresses
✅ Database query optimization (cardinality estimates)
✅ Stream processing (count unique events)Purpose: Estimate frequency of elements with bounded error
Traditional: Hash map → O(n) space, exact counts
Count-Min Sketch: Fixed memory → approximate counts with error boundimport hashlib
class CountMinSketch:
"""Frequency estimation"""
def __init__(self, width=1000, depth=7):
self.width = width
self.depth = depth
self.table = [[0] * width for _ in range(depth)]
def _hashes(self, item):
"""Generate d hash values"""
hashes = []
for i in range(self.depth):
hash_input = f"{item}:{i}".encode()
hash_val = int(hashlib.md5(hash_input).hexdigest(), 16)
hashes.append(hash_val % self.width)
return hashes
def add(self, item, count=1):
"""Increment count for item"""
for i, h in enumerate(self._hashes(item)):
self.table[i][h] += count
def estimate(self, item):
"""Estimate count (returns minimum across rows)"""
return min(self.table[i][h] for i, h in enumerate(self._hashes(item)))
# Usage
cms = CountMinSketch(width=1000, depth=7)
# Count events
for event in event_stream:
cms.add(event)
# Estimate frequency
print(f"Event X count: {cms.estimate('event_x')}") # Approximate count
# Never underestimates, may overestimate due to collisions✅ Heavy hitters detection (top-k frequent items)
✅ Network traffic analysis
✅ Query frequency estimation
✅ Rate limiting (count requests per user)| Structure | Purpose | Space | Accuracy | False Positives | |-----------|---------|-------|----------|-----------------| | Bloom Filter | Membership | O(1) per item | High | Yes (tunable) | | HyperLogLog | Cardinality | Fixed (~KB) | ~2% error | N/A | | Count-Min Sketch | Frequency | Fixed | Bounded error | Overestimates | | Hash Set | Membership | O(n) | 100% | No | | Hash Map | Frequency | O(n) | 100% | No |
# Large set, only need membership test
user_blacklist = BloomFilter(size=1000000)
if user_blacklist.contains(user_id):
# Might be blacklisted - check database
if database.is_blacklisted(user_id):
reject()# Count unique items in stream
unique_visitors = HyperLogLog()
for request in request_stream:
unique_visitors.add(request.user_id)
print(f"DAU: {unique_visitors.cardinality()}")# Track frequency, find heavy hitters
request_counts = CountMinSketch()
for request in request_stream:
request_counts.add(request.endpoint)
# Find most frequent endpoints
top_endpoints = [(e, request_counts.estimate(e)) for e in endpoints]
top_endpoints.sort(key=lambda x: x[1], reverse=True)# HyperLogLog for unique counting
PFADD unique_visitors user:123
PFCOUNT unique_visitors # Approximate count
# Bloom filter (via RedisBloom module)
BF.ADD bloom_filter "item"
BF.EXISTS bloom_filter "item"Uses Bloom filters for:
- SSTable filtering (avoid disk reads)
- Reduce false positive rate with multiple hash functionsdistributed-systems-eventual-consistency - Consistency trade-offsdistributed-systems-partitioning-sharding - Data distributiondistributed-systems-gossip-protocols - Epidemic algorithmsLast Updated: 2025-10-27