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 foverlapmean estrel.biasrel.RMSP(est<0)
0.505000049954-0.00090.0680.000
0.2020000205090.02540.1960.000
0.10100009971-0.00290.4210.013
0.0550004886-0.02280.8640.142
0.02200022260.11312.3250.307
0.011000581-0.41864.3860.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