Probabilistic Sketches
Cross-process probabilistic sketches
Approximate aggregations - sub-linear memory for the cardinality of values they see.
| Primitive | Answers |
|---|---|
| Shared Bit Vec | Dense set membership over a small key space |
| Shared Bloom Filter | “Has key X been seen?” with controlled false-positive rate |
| Shared Blocked Bloom Filter | Same membership at one cache line per query; wins past L3 |
| Shared Count-Min Sketch | Approximate counts per key without keeping the keys |
| Shared HyperLogLog | Distinct-count estimate with very low memory; one shared HLL accumulates the union across processes (no separate merge step) |
| Shared Histogram | Bucketed value distribution (latency, etc.) |
| Shared Reservoir Sampler | Uniform random sample from an unknown-size stream |
For the prose overview, see shared-sketches .