Bottom-k不同键摘要 | Codeboy's Blog

形式陈述

摘要保存键，名次来自共同排列

沿用MinHash的有限宇宙 U、大小 N 和共享均匀随机排列 $\pi$ 。容量 k 为正整数；对不同键集合 A，令 $K_k(A)$ 为 A 中名次最小的 $\min(k,|A|)$ 个键。摘要保存这些键及名次，并增加一个布尔位 complete，表示 $|A|\le k$ 、摘要是否包含整个集合。

输入允许同一键重复出现，但不允许改变该键的排列名次。只支持增加出现记录，不由此获得删除接口。两摘要合并前须核对宇宙、排列及容量相同；这些是结果有意义的前提。

对 $K_A=K_k(A)$ 、 $K_B=K_k(B)$ ，令 $C=K_k(K_A\cup K_B)$ 。有精确身份等式

C=K_k(A\cup B).

因此它是可合并摘要的一个集合实例：相同键跨片重放仍只占一个样本位置。若 C 非空，Jaccard估计量为

\widehat J_k=\frac{|C\cap K_A\cap K_B|}{|C|};

C 为空时按两空集约定输出1。对固定 A、B， $\mathbb E\widehat J_k=J(A,B)$ 。若 $n=|A\cup B|>k$ ，

\operatorname{Var}(\widehat J_k)= \frac{J(1-J)}k\frac{n-k}{n-1}.

当 $n\le k$ ，并集完全保存，估计等于真实 J，方差为零。[1, §3，Theorem 1；2, §2]

用第k名估计集合大小

假设 $k\ge2$ ，宇宙大小 N 已知。若 complete 为真，直接返回保留键数；否则令 R 为保留键中的最大名次，即集合的第 k 小顺序统计量，返回

\widehat n=\frac{N(k-1)}{R-1}.

这是有限排列模型下的无偏基数估计。分母是 R−1，不是 R；键名次在1到N间，不能当成连续均匀随机数而不改变公式。由于 R≥k≥2，分母严格为正。

直觉

只去重当前样本，为什么足够

用一个容量 k 的最大二叉堆保存候选，堆顶是当前保留者中最晚的名次；另用至多 k 个键的字典检查候选内重复。读到 x 时依次执行：

x 已在候选字典中：不变。
候选不足 k 项：加入 x。
候选已有 k 项且 x 不在其中：将 complete 置假；若 x 的名次小于堆顶，替换堆顶，否则丢弃。

不变量为“候选正是已读前缀不同键的前 k 名”。前两种情况直接成立；第三种只需把新键与前 k 名中最差者比较。一个已被淘汰或拒绝的键，其名次不早于当时阈值；此后阈值只能向更早方向移动，所以它再次出现也不可能重新入选。无须保存全部历史键，候选字典足以处理重复。

complete 初值为真。第一次在满堆时看到候选之外的键，说明至少出现过 k+1 个不同键，此后一直为假。若流从来只重复当前 k 个键，则不会误置假。这一位也区分“恰有 k 个不同键”和“超过 k 个，只保留 k 个”。

合并后只对共同的并集样本计数

若 x 属于 A 却不在 $K_A$ ，A 内已有 k 个比它更早的键，所以 x 不可能进入 $A\cup B$ 的前 k 名。对 B 同理，故全局前 k 名都在两局部摘要的候选并集中，合并等式成立。

进一步，若 $x\in C$ 且 $x\in A$ ，则 x 必在 $K_A$ ；否则刚才的 k 个更早键会排除它。于是对全局样本 C 中的键，只看它是否同时出现在两份局部摘要，便能正确判断它是否属于交集。局部没保留的键并非不存在；能够这样判断，是因为先限制到了 C。

同一排列下两份前二样本先合并截断，再在共同样本中标交集；直接比较局部样本的并集会得到不同分母。

均匀排列让 C 在并集的所有 k 元子集中等概率。令交集大小为 M。样本交集数 X 满足 $\mathbb EX=kM/n$ ；对两个不同样本位置，它们同时来自交集的概率为 $M(M-1)/(n(n-1))$ 。展开 $X^2$ 后得到 $\operatorname{Var}X=kJ(1-J)(n-k)/(n-1)$ ，除以 $k^2$ 就是前述方差。末尾的有限总体修正反映无放回抽样，不是独立副本修正。

有限名次公式的完整核算

固定 A 的大小 n≥k。它的 n 个名次是 $\{1,\ldots,N\}$ 的均匀 n 元子集。第 k 小名次恰为 r，需要从前 r−1 个名次选 k−1 个，再从后 N−r 个名次选 n−k 个，因此

\Pr(R=r)=\frac{\binom{r-1}{k-1}\binom{N-r}{n-k}}{\binom Nn}, \qquad k\le r\le N-n+k.

把 $N(k-1)/(r-1)$ 乘进去，使用

\frac{k-1}{r-1}\binom{r-1}{k-1}=\binom{r-2}{k-2}.

余下的和 $\sum_r\binom{r-2}{k-2}\binom{N-r}{n-k}$ 等于 $\binom{N-1}{n-1}$ ：在 N−1 个位置中选 n−1 个，按其中第 k−1 个选中位置是 r−1 分组，即得到左式。于是

\mathbb E\widehat n= N\frac{\binom{N-1}{n-1}}{\binom Nn}=n.

若 n≤k，complete 分支精确返回 n，也无偏。这个证明不需要大宇宙近似。

例子与边界

两种分母在四键例中已经不同

令 $A=\{0,1,2\}$ 、 $B=\{1,2,3\}$ ，k=2，排列次序为0、1、2、3。局部样本是 $K_A=\{0,1\}$ 、 $K_B=\{1,2\}$ ，全局样本 $C=\{0,1\}$ 。其中只有1属于交集，所以正确估计为1/2。

若误算 $|K_A\cap K_B|/|K_A\cup K_B|$ ，得到1/3。它不是同一估计量的小幅实现差异：枚举全部24个排列，这个朴素比值的平均为4/9，而真实 J 与正确估计的平均都为1/2。

小样本、空集与超过真实值的单次估计

在 N=6 的宇宙中，k=2、A有三个键，若它们恰占名次1、2、3，则 R=2，估计为6；若名次为2、3、4，则 R=3，估计为3。第一份样本高估并不违背无偏性，无偏说的是遍历随机排列后的平均。

若N=6、k=2且真实n=3，R取2、3、4、5的概率依次为4/20、6/20、6/20、4/20，对应估计6、3、2、3/2，平均恰为3。最后一种甚至低于已知至少保存的两个键；若强行将估计截断到至少2，平均就升成31/10。约束看起来更合理，也可能破坏已证明的精确无偏性。

k=1仍可计算前述相似度估计，但本页非平凡基数公式要求k≥2。若只出现一个键，complete为真仍可精确返回1；若后来出现第二个不同键，容量1的对象应拒绝调用此基数公式，而不是返回分子为零的结果。

k大于宇宙大小没有逻辑问题：永远保存全集。两侧都是完整摘要，但合并候选数超过k时，合并后complete仍须变假；仅将两侧complete作逻辑与是不够的。

共同随机源与删除能力

两个分片即使保留数量相同，若各用不同排列，合并取最小名次没有统一含义。调用端不能只核“都是64位整数”；宇宙编码、随机源身份、容量和去重语义也须一致。

删除一个保留键时，下一个候选可能曾被丢弃。例如k=2、已见名次1、2、3，摘要只含1、2；删除1后应补3，却已经不知道3的身份。重新扫描、额外索引或专门动态结构可以处理删除，但不属于这份 O(k) 插入式摘要的保证。

推论与应用

合并实现、时间和存储

合并将两份候选并集去重后逐项插入一个新堆。complete设置为“两侧complete都真，且候选并集大小不超过k”。每份候选至多k项，故堆工作为 $O(k\log(k+1))$ ，存储为 $O(k)$ 个记录。字典用期望常数查询时，长度L的更新总成本为 $O(L\log(k+1)+1)$ ；若要确定最坏界，可用平衡树去重，仍在这一数量级内。这里把键、名次装入机器字，长键和大整数成本另计。

参考实现为完全核实共同排列，会比较两份长度N的名次数组，所以一次merge或Jaccard调用实际还有 $O(N)$ 兼容性成本。工程接口若拥有可信、无歧义的公共配置身份，才可把这项核验降为常数。展示全部候选的排序例程另需 $O(k\log(k+1))$ ，不是更新时必须完成的工作。

存储的 O(k) 指每个集合的状态，共用有限排列仍占 O(N)。经典连续名次版本使用独立 $U_x\sim U(0,1)$ ，基数公式为 $(k-1)/U_{(k)}$ ；有限排列版的 R/N具有离散分布，不应直接套成 $N(k-1)/R$ 。

完整的报告对象

共享随机键终结任务将两份流的重复键、前k候选、complete位、合并样本及交集标记全部保存。读者还要复算N≤6的有限排列基数平均，并构造删除后无法恢复下一名的两种原集合。这既检查程序状态，也检查它实际上估计什么。

参考资料

[1] Andrei Z. Broder，On the Resemblance and Containment of Documents，1997，§3 Theorem 1的固定容量并集样本公式，§4.1的堆与候选去重，§4.2的无放回计数。

[2] Edith Cohen、Haim Kaplan，Summarizing Data using Bottom-k Sketches，PODC，2007，§2的协调rank与bottom-k定义。本文的有限排列基数公式、complete位及删除反例由所声明模型独立推导；没有将所有加权rank分布混成均匀不同键抽样。

形式陈述 ​

摘要保存键，名次来自共同排列 ​

用第k名估计集合大小 ​

只去重当前样本，为什么足够 ​

合并后只对共同的并集样本计数 ​

有限名次公式的完整核算 ​

两种分母在四键例中已经不同 ​

小样本、空集与超过真实值的单次估计 ​

共同随机源与删除能力 ​

合并实现、时间和存储 ​

完整的报告对象 ​

反向链接