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 n | 600000; exact set of 64-bit keys = 4687.5 KB |
| bits/key k filter KB FP rate store lookups/day saved | |
| 6 | 4 439.5 0.05606 1221.1 0.939 |
| 8 | 6 585.9 0.02158 531.5 0.974 |
| 10 | 7 732.4 0.00819 263.9 0.987 |
| 12 | 8 878.9 0.00314 162.8 0.992 |
| 16 11 | 1171.9 0.00046 109.2 0.995 |
| if the filter alone rejected orders, at 10 bits/key: | |
| genuine orders refused per day | 163.9 |
| chance of at least one refusal per day | 1.000000 |
| refused per 30-day window | 4916 |
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
- Chapter 1 · The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up
- 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 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