Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes: chapter answers

Operators who run a hundred sites often add up the unique visitors on each site's dashboard and call the total the network's audience, keep every order number in an ever-longer table to compare against, and trust the textbook false-positive formula of the Bloom filter as exact. This book refutes all three beliefs. Exact deduplication does need linear memory, and that is proven; but once randomisation and approximation are both accepted, counting any number of distinct visitors takes 3072 bytes at a standard error of 0.0163. In an illustrative network, per-site unique visitors add up to 2.224…

DOI pending · monograph page goes live after publication · 5DL-B-294 · 中文版

Illustrative model calculation, not a live quote