What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “Merging a Hundred Sites, the Intersection Trap and the Privacy of Registers”?
Answer: 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 one more person changes the sketch with probability 0.9935.
Scope of the numbers: In an illustrative network, per-site unique visitors add up to 2.224 times the true number of people. Marked boxes separate published evidence, Python calculations (20 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.10, 0.421
| share f | overlap | mean est | rel.bias | rel.RMS | P(est<0) |
| 0.50 | 50000 | 49954 | -0.0009 | 0.068 | 0.000 |
| 0.20 | 20000 | 20509 | 0.0254 | 0.196 | 0.000 |
| 0.10 | 10000 | 9971 | -0.0029 | 0.421 | 0.013 |
| 0.05 | 5000 | 4886 | -0.0228 | 0.864 | 0.142 |
| 0.02 | 2000 | 2226 | 0.1131 | 2.325 | 0.307 |
| 0.01 | 1000 | 581 | -0.4186 | 4.386 | 0.455 |
| union and single-site SE at m = 1024: 0.0325 |
Show the full program
# Chapter 6. p62: overlaps by subtraction are only as good as the overlap
# is large. Two sites A and B, |A| = |B| = 100,000 visitors, a share f of
# them common; m = 1024 registers each. Inclusion-exclusion:
# |A and B| = |A| + |B| - |A or B|. Registers are drawn exactly under
# the Poisson model of p22 for the three disjoint parts (A only, B only,
# both); a site's register is the max of its parts, and the union's is
# the max of all three. 400 trials per f.
import math
import random
rng = random.Random(20261113)
M, T, SIZE = 1024, 400, 100000
ALPHA = 0.7213 / (1.0 + 1.079 / M)
def draw(lam):
u = rng.random()
while u == 0.0:
u = rng.random()
x = lam / -math.log(u)
return 0 if x <= 1.0 else math.ceil(math.log2(x))
def est(regs):
return ALPHA * M * M / math.fsum(2.0 ** -r for r in regs)
print(" share f overlap mean est rel.bias rel.RMS P(est<0)")
for f in (0.5, 0.2, 0.1, 0.05, 0.02, 0.01):
both = f * SIZE
only = SIZE - both
rel, neg = [], 0
for _ in range(T):
a = [draw(only / M) for _ in range(M)]
b = [draw(only / M) for _ in range(M)]
c = [draw(both / M) for _ in range(M)]
ra = [max(x, z) for x, z in zip(a, c)]
rb = [max(y, z) for y, z in zip(b, c)]
ru = [max(x, y, z) for x, y, z in zip(a, b, c)]
i = est(ra) + est(rb) - est(ru)
rel.append(i / both - 1.0)
if i < 0:
neg += 1
mu = math.fsum(rel) / T
rms = math.sqrt(math.fsum(r * r for r in rel) / T)
print("%8.2f %8.0f %10.0f %9.4f %8.3f %9.3f"
% (f, both, both * (1 + mu), mu, rms, neg / T))
print("union and single-site SE at m = %d: %.4f"
% (M, 1.04 / math.sqrt(M)))Single source and citation
Fan, Y. (2026). Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes (Version 1.0.0), Chapter 6: Merging a Hundred Sites, the Intersection Trap and the Privacy of Registers. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026294,
author = {Fan, Yafu},
title = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up
- Chapter 2 · HyperLogLog: the First 1-Bit, the Harmonic Mean and 1.04/√m
- Chapter 3 · Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width
- Chapter 4 · The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space
- Chapter 5 · Order Deduplication: Filters Route but Never Reject, Windows Rotate by Generation, Counters Delete
- Chapter 7 · Classical Sources East and West: the Registration Rule of the Minor Minister and Laplace's Ratio of Births
- Chapter 8 · Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit