关于「百站合并、交集陷阱与寄存器的隐私」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第六章合并一百个站点的草图,指出共有比例 0.10 时交集估计的相对误差达 0.421,并说明寄存器不是匿名的:访客稀少时再加一人使草图改变的概率是 0.9935。

数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.10, 0.421

share foverlapmean estrel.biasrel.RMSP(est<0)
0.505000049954-0.00090.0680.000
0.2020000205090.02540.1960.000
0.10100009971-0.00290.4210.013
0.0550004886-0.02280.8640.142
0.02200022260.11312.3250.307
0.011000581-0.41864.3860.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}
}

本书其他章节结论