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 logged834564
sum of site uniques333606
true unique visitors150000
overstatement factor2.224
top site uniques36187
HLL union estimate153319.2
HLL relative error0.0221
nominal 1.04/sqrt(m)0.0163
100 sketches, bytes307200
exact union as hashes1200000 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