What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “Order Deduplication: Filters Route but Never Reject, Windows Rotate by Generation, Counters Delete”?

Answer: Chapter 5 rules that the filter routes and never rejects: lookups fall by 0.987, while rejecting on the filter would wrongly refuse 4916 real orders in thirty days; the window rotates in two generations, deletion needs a counting filter, and clearing bits in an ordinary filter makes 0.3944 of live orders read as unseen.

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.987, 4916

keys held n600000; exact set of 64-bit keys = 4687.5 KB
bits/key k filter KB FP rate store lookups/day saved
64 439.5 0.05606 1221.1 0.939
86 585.9 0.02158 531.5 0.974
107 732.4 0.00819 263.9 0.987
128 878.9 0.00314 162.8 0.992
16 111171.9 0.00046 109.2 0.995
if the filter alone rejected orders, at 10 bits/key:
genuine orders refused per day163.9
chance of at least one refusal per day1.000000
refused per 30-day window4916
Show the full program
# Chapter 5. p51: a Bloom filter may route orders, never reject them.
# Illustrative network: 100 sites, 20,000 new orders a day plus 100
# resubmissions (double clicks, client retries); a 30-day dedup window,
# so n = 600,000 order keys are held. Gate: "definitely new" from the
# filter goes straight through; "maybe seen" goes to the exact order
# store. FP rate from the closed form at the best integer k; the exact
# rate is slightly higher (p43), negligible at this size.
import math

NEW, DUP, DAYS = 20000, 100, 30
N = NEW * DAYS


def fp(c):
    k = min(range(1, 40), key=lambda j: (1 - math.exp(-j / c)) ** j)
    return k, (1 - math.exp(-k / c)) ** k


print("keys held n = %d; exact set of 64-bit keys = %.1f KB"
      % (N, N * 8 / 1024))
print("bits/key  k  filter KB   FP rate  store lookups/day  saved")
for c in (6, 8, 10, 12, 16):
    k, p = fp(c)
    look = DUP + p * NEW
    print("%8d %2d %10.1f %9.5f %18.1f %6.3f"
          % (c, k, c * N / 8 / 1024, p, look, 1 - look / (NEW + DUP)))
k, p = fp(10)
print("if the filter alone rejected orders, at 10 bits/key:")
print("  genuine orders refused per day: %.1f" % (p * NEW))
print("  chance of at least one refusal per day: %.6f"
      % (1 - (1 - p) ** NEW))
print("  refused per 30-day window: %.0f" % (p * NEW * DAYS))

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 5: Order Deduplication: Filters Route but Never Reject, Windows Rotate by Generation, Counters Delete. 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