What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width”?

Answer: Chapter 3 handles both ends: below 2.5 times the register count linear counting takes over, with a positive bias of 0.0144 at the switch point, and a 32-bit hash loses 0.1079 of a billion visitors.

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.1079, 32

threshold 2^32 / 30143165577
distinct n32-bit seen undercount 64-bit undercount
1e+06999884 0.0001 2.71e-14
1e+079988367 0.0012 2.71e-13
1e+0898844829 0.0116 2.71e-12
1.432e+08140839071 0.0165 3.88e-12
5e+08471993428 0.0560 1.36e-11
1e+09892117359 0.1079 2.71e-11
2e+091598931006 0.2005 5.42e-11
4e+092602611761 0.3493 1.08e-10
n1e+09: corrected 1000000000, error amplified by 1.262
n4e+09: corrected 4000000000, error amplified by 2.538
hash 32 bits, b12: max register 21, needs 5 bits
hash 64 bits, b12: max register 53, needs 6 bits
hash 64 bits, b14: max register 51, needs 6 bits
Show the full program
# Chapter 3. p32: a 32-bit hash runs out of room; a 64-bit hash does not.
# With an L-bit hash, n distinct items occupy about 2^L (1 - exp(-n/2^L))
# distinct hash values (balls in bins), so even a perfect sketch of the
# hash values undercounts. Flajolet et al. (2007) invert this above
# 2^32 / 30; the inversion is exact in expectation but multiplies any
# relative error in E by exp(n / 2^L), the slope of the inverse.
# Register width: values run up to L + 1 - b, so 5 bits for L = 32 and
# 6 bits for L = 64. Item counts below are illustrative.
import math


def occupied(n, bits):
    return 2.0 ** bits * -math.expm1(-n / 2.0 ** bits)


def corrected(e, bits):
    return -(2.0 ** bits) * math.log1p(-e / 2.0 ** bits)


print("threshold 2^32 / 30 = %.0f" % (2.0 ** 32 / 30))
print("  distinct n   32-bit seen  undercount  64-bit undercount")
for n in (1e6, 1e7, 1e8, 1.432e8, 5e8, 1e9, 2e9, 4e9):
    s32 = occupied(n, 32)
    s64 = occupied(n, 64)
    print("%12.4g %13.0f %11.4f %18.2e"
          % (n, s32, 1.0 - s32 / n, 1.0 - s64 / n))
for n in (1e9, 4e9):
    print("n = %.0e: corrected %.0f, error amplified by %.3f"
          % (n, corrected(occupied(n, 32), 32), math.exp(n / 2.0 ** 32)))
for bits, b in ((32, 12), (64, 12), (64, 14)):
    top = bits + 1 - b
    print("hash %d bits, b = %d: max register %d, needs %d bits"
          % (bits, b, top, top.bit_length()))

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 3: Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width. 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