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
13267 3231 4150 4210
24583 4577 4071 4004
33822 3832 3123 3113
42785 2774 5875 5830
55607 5562 2873 2922
64736 4789 4574 4507
74115 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
stored14 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