Working with Probabilistic Data Structures
1. Understanding Bloom Filters
| Property | Detail |
|---|---|
| Operation | Add + membership query (no delete) |
| Errors | False positive possible; false negative never |
| Optimal hashes | k = (m/n) × ln(2) |
| FP rate | (1 − e^(−kn/m))^k |
| Use cases | Cache pre-check, dedup, LSM SST filter |
Example: Guava BloomFilter
BloomFilter<String> bf = BloomFilter.create(
Funnels.stringFunnel(StandardCharsets.UTF_8),
1_000_000, // expected insertions
0.01); // false positive rate
bf.put("user:42");
bf.mightContain("user:42"); // true
bf.mightContain("user:99"); // probably false2. Implementing Counting Bloom Filters
| Property | Detail |
|---|---|
| Cells | 4-bit counters instead of bits |
| Supports | Add, remove, query |
| Cost | ~4× space of standard Bloom |
| Risk | Counter overflow (cap at max) |
3. Implementing HyperLogLog
| Property | Value |
|---|---|
| Purpose | Approximate cardinality (distinct count) |
| Memory | ~12KB for <2% error |
| Standard error | 1.04 / √m |
| Mergeable | Yes — combines for federated count |
| Used by | Redis PFCOUNT, BigQuery APPROX_COUNT_DISTINCT |
4. Understanding Count-Min Sketch
| Property | Detail |
|---|---|
| Purpose | Approximate frequency of items in stream |
| Structure | d × w matrix; d hash functions |
| Error bound | Overestimate ≤ ε·N with prob 1−δ |
| Use cases | Heavy hitters, network anomaly detection |
5. Implementing Cuckoo Filters
| Property | Detail |
|---|---|
| vs Bloom | Supports delete; better space-efficiency at low FP |
| Mechanism | Cuckoo hashing of fingerprints |
| Lookup | 2 buckets only; very fast |
| Risk | Insert failure when load > ~95% |
6. Understanding MinHash for Similarity
| Property | Detail |
|---|---|
| Purpose | Estimate Jaccard similarity of sets |
| Mechanism | k hash functions; record min hash per set |
| Estimate | Fraction of matching min-hashes |
| Used by | Near-duplicate detection (LSH), recommendations |
7. Implementing Approximate Membership Queries
| Structure | Best For |
|---|---|
| Bloom | Static sets, no delete |
| Counting Bloom | Dynamic with delete |
| Cuckoo | Lower FP rate, supports delete |
| Quotient filter | Cache-friendly, mergeable |
8. Understanding False Positive Rates
| Filter | Bits/element @ 1% FP |
|---|---|
| Bloom | ~9.6 |
| Counting Bloom (4-bit) | ~38 |
| Cuckoo (16-bit fingerprint) | ~13 |
| Quotient | ~12 |
9. Implementing Space-Efficient Counting
| Structure | Use Case |
|---|---|
| HyperLogLog | Distinct count |
| Count-Min Sketch | Frequency per item |
| Top-K (Stream-Summary) | Heavy hitters |
| T-Digest / DDSketch | Streaming quantiles |
10. Understanding Trade-offs in Probabilistic Structures
| Trade | Detail |
|---|---|
| Space ↓ vs Accuracy ↓ | Tunable via parameters |
| Speed ↑ | O(1) operations |
| No exact answers | Best for "good enough" use cases |
| Mergeability | Critical for distributed aggregation |