probabilistic-structures-trade-accuracy-for-space

Status: IN

Three systems deploy probabilistic data structures with explicitly tunable accuracy-space tradeoffs: HyperLogLog with 16384 registers for ~1% cardinality error, Morris counters averaging 32 independent estimators for approximate counting, and SimHash with a 3-bit Hamming threshold for near-duplicate detection — each accepting bounded inaccuracy to achieve sub-linear space consumption.

Justifications

Depended on by

• approximation-spans-counting-windowing-and-similarity
• memory-is-bounded-at-the-cost-of-silent-information-loss
• probabilistic-dedup-trades-memory-for-coverage

JSON