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 · 中文版
- Chapter 1 · The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up
The memory of exact deduplication is almost proportional to the count: at a hundred million visitors the information floor is 485.841 MB, 158151 times a sketch of 3072 bytes. This is not a shortfall of engineering but a… - Chapter 2 · HyperLogLog: the First 1-Bit, the Harmonic Mean and 1.04/√m
Chapter 2 opens HyperLogLog, recomputes the limiting constant 1.03896, and shows that the constant is 1.106 at m = 16 and that the abstract's example of 1.5 kilobytes corresponds to a standard error of 0.0230. - Chapter 3 · Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width
Chapter 3 handles both ends: below 2.5 times the register count linear counting takes over, with a positive bias of 0.0144 at the switch point, and a 32-bit hash loses 0.1079 of a billion visitors. - Chapter 4 · The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space
Chapter 4 measures Bloom filters and explains the optimal probe count and the space factor of 1.443. - Chapter 5 · Order Deduplication: Filters Route but Never Reject, Windows Rotate by Generation, Counters Delete
Chapter 5 rules that the filter routes and never rejects: lookups fall by 0.987, while rejecting on the filter would wrongly refuse 4916 real orders in thirty days; the window rotates in two generations, deletion needs… - Chapter 6 · Merging a Hundred Sites, the Intersection Trap and the Privacy of Registers
Chapter 6 merges the sketches of a hundred sites, shows that at a shared share of 0.10 the intersection estimate has a relative error of 0.421, and explains that registers are not anonymous: with few visitors, adding on… - Chapter 7 · Classical Sources East and West: the Registration Rule of the Minor Minister and Laplace's Ratio of Births
Chapter 7 examines the registration rule of the Minor Minister in the Zhou li and Laplace's ratio of births, recomputes Laplace's required count of 771469 people, and notes that the same precision needs only 24576 bytes… - Chapter 8 · Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit
Chapter 8 gives a registers-only weekly procedure for tollbooth and direct-answer pages, the Cardinality Estimator and a pre-registered audit plan: in the demonstration week the union of two pages is estimated at 35420…
Illustrative model calculation, not a live quote