Bloom Filters, HyperLogLog, and Count-Min Sketch: the data…
0 reactions
Bloom Filters, HyperLogLog, and Count-Min Sketch: the data structures powering approximate databases
A writeup on probabilistic databases: systems that deliberately trade a small, bounded error for dramatic gains in speed and memory efficiency. The interesting part is the underlying CS: HyperLogLog estimates cardinality of billions of elements with \~1% error using a few KB of memory, Bloom filters answer set membership with zero false negatives, and Count-Min Sketch tracks frequencies in a stream without storing the stream. The post covers how these structures work and how engines like Druid and ClickHouse use them in production.
#technology
A writeup on probabilistic databases: systems that deliberately trade a small, bounded error for dramatic gains in speed and memory efficiency. The interesting part is the underlying CS: HyperLogLog estimates cardinality of billions of elements with \~1% error using a few KB of memory, Bloom filters answer set membership with zero false negatives, and Count-Min Sketch tracks frequencies in a stream without storing the stream. The post covers how these structures work and how engines like Druid and ClickHouse use them in production.
#technology
| 2,000 mlx | |
| 4 | |
| 0 |