关于「百站合并、交集陷阱与寄存器的隐私」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第六章合并一百个站点的草图,指出共有比例 0.10 时交集估计的相对误差达 0.421,并说明寄存器不是匿名的:访客稀少时再加一人使草图改变的概率是 0.9935。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.10, 0.421
| share f | overlap | mean est | rel.bias | rel.RMS | P(est<0) |
| 0.50 | 50000 | 49954 | -0.0009 | 0.068 | 0.000 |
| 0.20 | 20000 | 20509 | 0.0254 | 0.196 | 0.000 |
| 0.10 | 10000 | 9971 | -0.0029 | 0.421 | 0.013 |
| 0.05 | 5000 | 4886 | -0.0228 | 0.864 | 0.142 |
| 0.02 | 2000 | 2226 | 0.1131 | 2.325 | 0.307 |
| 0.01 | 1000 | 581 | -0.4186 | 4.386 | 0.455 |
| union and single-site SE at m = 1024: 0.0325 |
查看完整验算程序
# Chapter 6. p62: overlaps by subtraction are only as good as the overlap
# is large. Two sites A and B, |A| = |B| = 100,000 visitors, a share f of
# them common; m = 1024 registers each. Inclusion-exclusion:
# |A and B| = |A| + |B| - |A or B|. Registers are drawn exactly under
# the Poisson model of p22 for the three disjoint parts (A only, B only,
# both); a site's register is the max of its parts, and the union's is
# the max of all three. 400 trials per f.
import math
import random
rng = random.Random(20261113)
M, T, SIZE = 1024, 400, 100000
ALPHA = 0.7213 / (1.0 + 1.079 / M)
def draw(lam):
u = rng.random()
while u == 0.0:
u = rng.random()
x = lam / -math.log(u)
return 0 if x <= 1.0 else math.ceil(math.log2(x))
def est(regs):
return ALPHA * M * M / math.fsum(2.0 ** -r for r in regs)
print(" share f overlap mean est rel.bias rel.RMS P(est<0)")
for f in (0.5, 0.2, 0.1, 0.05, 0.02, 0.01):
both = f * SIZE
only = SIZE - both
rel, neg = [], 0
for _ in range(T):
a = [draw(only / M) for _ in range(M)]
b = [draw(only / M) for _ in range(M)]
c = [draw(both / M) for _ in range(M)]
ra = [max(x, z) for x, z in zip(a, c)]
rb = [max(y, z) for y, z in zip(b, c)]
ru = [max(x, y, z) for x, y, z in zip(a, b, c)]
i = est(ra) + est(rb) - est(ru)
rel.append(i / both - 1.0)
if i < 0:
neg += 1
mu = math.fsum(rel) / T
rms = math.sqrt(math.fsum(r * r for r in rel) / T)
print("%8.2f %8.0f %10.0f %9.4f %8.3f %9.3f"
% (f, both, both * (1 + mu), mu, rms, neg / T))
print("union and single-site SE at m = %d: %.4f"
% (M, 1.04 / math.sqrt(M)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 6 章「百站合并、交集陷阱与寄存器的隐私」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}