What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up”?
Answer: 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 proven result: a deterministic algorithm needs linear memory even to approximate within a tenth, and a randomised algorithm needs linear memory to be exact; only when randomisation and approximation are both accepted can memory stop depending on the count. Adding up per-site unique visitors overstated the illustrative network by a factor of 2.224; merging a hundred sketches by register maximum gave an error of 0.0221 in 307200 bytes. The next chapter opens HyperLogLog itself: why the position of the first 1-bit can count people, why a harmonic mean beats a geometric one, and where the constant in 1.04/√m comes from and how accurate it really is.
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.0221, 1.04, 2.224, 307200
| visits logged | 834564 |
| sum of site uniques | 333606 |
| true unique visitors | 150000 |
| overstatement factor | 2.224 |
| top site uniques | 36187 |
| HLL union estimate | 153319.2 |
| HLL relative error | 0.0221 |
| nominal 1.04/sqrt(m) | 0.0163 |
| 100 sketches, bytes | 307200 |
| exact union as hashes | 1200000 bytes |
Show the full program
# Chapter 1. p12: adding up site uniques overstates the network's reach.
# Illustrative network: 100 sites whose popularity falls as 1/rank^0.8;
# 150,000 visitors; each visits 1 + Geometric(0.45) sites (capped at 12)
# and makes 1 to 4 visits per site. Exact per-site sets and the exact
# union are counted; the sum of site uniques is what a report gets when
# it adds per-site dashboards together. Then one HyperLogLog sketch per
# site (m = 4096, keyed BLAKE2b, 64-bit) is merged by register maximum.
import bisect
import hashlib
import math
import random
rng = random.Random(20261113)
SITES, PEOPLE, M, B = 100, 150000, 4096, 12
W = [1.0 / (r + 1) ** 0.8 for r in range(SITES)]
CUM = [math.fsum(W[:i + 1]) for i in range(SITES)]
KEY = b"b294-illustrative-window-key"
ALPHA = 0.7213 / (1.0 + 1.079 / M)
def h64(text):
d = hashlib.blake2b(text.encode(), digest_size=8, key=KEY).digest()
return int.from_bytes(d, "big")
def add(regs, x):
j = x >> (64 - B)
w = x & ((1 << (64 - B)) - 1)
rho = (64 - B) - w.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
site_sets = [set() for _ in range(SITES)]
sketches = [[0] * M for _ in range(SITES)]
visits = 0
for p in range(PEOPLE):
k = 1
while k < 12 and rng.random() > 0.45:
k += 1
chosen = set()
while len(chosen) < k:
u = rng.random() * CUM[-1]
chosen.add(min(SITES - 1, bisect.bisect_left(CUM, u)))
x = h64("visitor-%06d" % p)
for s in sorted(chosen):
for _ in range(rng.randint(1, 4)):
site_sets[s].add(p)
add(sketches[s], x)
visits += 1 # step
union = set()
for s in site_sets:
union |= s
added = int(math.fsum(len(s) for s in site_sets))
merged = [max(col) for col in zip(*sketches)]
est = estimate(merged)
print("visits logged %9d" % visits)
print("sum of site uniques %9d" % added)
print("true unique visitors %9d" % len(union))
print("overstatement factor %9.3f" % (added / len(union)))
print("top site uniques %9d" % len(site_sets[0]))
print("HLL union estimate %11.1f" % est)
print("HLL relative error %9.4f" % (est / len(union) - 1.0))
print("nominal 1.04/sqrt(m) %9.4f" % (1.04 / math.sqrt(M)))
print("100 sketches, bytes %9d" % (SITES * M * 6 // 8))
print("exact union as hashes %9d bytes" % (8 * len(union)))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 1: The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up. 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 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
- Chapter 8 · Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit