What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit”?
Answer: 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 against an audit of 35818, the spread test needs 70 page-days and the order gate 3463 keys known to be new. Marked boxes separate published evidence, Python calculations (20 programs), classical sources and the author's hypotheses.
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: 35420, 35818
| day T est T audit A est A audit | |
| 1 | 3267 3231 4150 4210 |
| 2 | 4583 4577 4071 4004 |
| 3 | 3822 3832 3123 3113 |
| 4 | 2785 2774 5875 5830 |
| 5 | 5607 5562 2873 2922 |
| 6 | 4736 4789 4574 4507 |
| 7 | 4115 4155 5759 5807 |
| week T 21137 (audit 21281), week A 18298 (audit 18563) | |
| week union 35420 (audit 35818) | |
| week overlap 4014 (audit 4026), share 0.113, FLAG: unreliable | |
| daily SE 0.0163; overlap shares below 0.2 are flagged | |
| stored | 14 sketches x 3072 bytes = 43008 bytes, no identifiers |
Show the full program
# Chapter 8. p81: one week of unique visitors on two pages, registers
# only. Illustrative traffic: page T (a tollbooth page) draws from a pool
# of 40,000 people, page A (a direct-answer page) from 25,000, with
# 10,000 in both pools; 2,500 to 6,000 people a day per page, 1 to 3
# hits each. Identifiers are hashed with a key that lives for one
# weekly window only; each page keeps one m = 4096 sketch per day
# (3,072 bytes). Weekly figures are register-wise maxima. Exact sets
# exist here only as the audit column; the daily pipeline keeps none.
# Counts under 50 would be shown as "<50" (none occur here).
import hashlib
import math
import random
rng = random.Random(20261113)
M, B, DAYS = 4096, 12, 7
ALPHA = 0.7213 / (1.0 + 1.079 / M)
WINDOW_KEY = b"b294-demo-window-label"
POOLS = {"T": range(0, 40000), "A": range(30000, 55000)}
def h64(text):
d = hashlib.blake2b(text.encode(), digest_size=8, key=WINDOW_KEY)
return int.from_bytes(d.digest(), "big")
def add(regs, x):
j = x >> (64 - B)
rho = (64 - B) - (x & ((1 << (64 - B)) - 1)).bit_length() + 1
if rho > regs[j]:
regs[j] = rho
def estimate(regs):
e = ALPHA * M * M / math.fsum(2.0 ** -r for r in regs)
v = regs.count(0)
if e <= 2.5 * M and v > 0:
return M * math.log(M / v)
return e
def shown(x):
return "<50" if x < 50 else "%.0f" % x
daily = {p: [] for p in POOLS}
audit = {p: [] for p in POOLS}
print("day T est T audit A est A audit")
for day in range(1, DAYS + 1):
row = []
for page, pool in POOLS.items():
regs, seen = [0] * M, set()
for person in rng.sample(pool, rng.randint(2500, 6000)):
x = h64("visitor-%06d" % person)
for _ in range(rng.randint(1, 3)):
add(regs, x)
seen.add(person)
daily[page].append(regs)
audit[page].append(seen)
row += [shown(estimate(regs)), len(seen)]
print("%3d %7s %8d %7s %8d" % (day, row[0], row[1], row[2], row[3]))
week = {p: [max(c) for c in zip(*daily[p])] for p in POOLS}
exact = {p: set().union(*audit[p]) for p in POOLS}
both = [max(a, b) for a, b in zip(week["T"], week["A"])]
eu = estimate(both)
inter = estimate(week["T"]) + estimate(week["A"]) - eu
ex_i = len(exact["T"] & exact["A"])
print("week T %.0f (audit %d), week A %.0f (audit %d)"
% (estimate(week["T"]), len(exact["T"]), estimate(week["A"]),
len(exact["A"])))
print("week union %.0f (audit %d)" % (eu, len(exact["T"] | exact["A"])))
flag = "FLAG: unreliable" if inter / eu < 0.2 else "ok"
print("week overlap %.0f (audit %d), share %.3f, %s"
% (inter, ex_i, inter / eu, flag))
print("daily SE %.4f; overlap shares below 0.2 are flagged"
% (1.04 / math.sqrt(M)))
print("stored: %d sketches x %d bytes = %d bytes, no identifiers"
% (2 * DAYS, M * 6 // 8, 2 * DAYS * M * 6 // 8))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 8: Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit. 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 6 · Merging a Hundred Sites, the Intersection Trap and the Privacy of Registers
- Chapter 7 · Classical Sources East and West: the Registration Rule of the Minor Minister and Laplace's Ratio of Births