LSH 放大候选索引

形式陈述 ​

从一对对象的碰撞到一批记录的索引 ​

输入是静态记录表 $P=(({\mathrm{id}}_i,x_i){)}_{i=1}^n$，允许 $n=0$。ID 必须唯一；两个 ID 可以携带完全相同的值，它们仍是两条应分别报告的记录。再给出基础随机函数族 $\mathcal{H}$、整数 $k,L\ge 1$，以及用于最终核验的确定谓词 $\mathrm{close}(x,z)$。

对每张表 $j\in \{0,\dots ,L-1\}$，抽取 $k$ 个基础函数，形成长度为 $k$ 的完整复合键

全部 $Lk$ 次抽样相互独立理路独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。，而数据与查询在每个分量上使用同一函数。表 $j$ 在键 $K_j(x_i)$ 下追加 ID，桶内保留输入顺序。键的相等是整个元组相等；用哈希表理路哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。存桶时，底层散列冲突仍由完整键比较处理，不能把底层散列值相等误当作相似性碰撞。

查询 $z$ 依表号从小到大遍历 $K_j(z)$ 的桶。第一次见到某个 ID 才计算 $\mathrm{close}(x_i,z)$；后面同一 ID 再出现只记一次重复出现，不再核验或输出。输出由已核验且谓词为真的 ID 组成，按首次见到的次序排列。因此所有返回值都满足核验谓词，但没返回的记录可能没有命中任何桶。

公开参考支持两种基础族。超平面角度指纹理路随机超平面角度指纹Random hyperplane angular sketch · Random hyperplane fingerprint在共享超平面配置下把非零方向编码为规范位串，以失配比例估计归一化夹角，并区分固定对象保证与自适应重用。提供共享符号序列，连续切成 $L$ 段、每段 $k$ 位；核验整数向量的余弦是否至少为给定有理数 $a/b\in [0,1]$。MinHash理路MinHash集合指纹MinHash · Min-wise hashing用所有集合共享的随机排列挑出最小键，以碰撞概率估计集合Jaccard相似度，并区分独立副本、重复键与哈希族偏差。则为有限全集中的非空集合提供共享排列最小元素，核验 Jaccard 比是否至少为 $a/b$。小全集参考保存完整排列，而不是用普通整数散列冒充严格 min-wise 抽样。给定函数表可以确定地执行索引；程序不能仅凭函数值检查调用者是否真的独立抽样。

AND 与 OR 分别使用哪一份独立性 ​

对抽样前固定的 $x,z$，令基础碰撞概率为 $p=\text{Pr}[h(x)=h(z)]$。同一张表的 $k$ 个独立分量全相等，才有键相等，所以

不同表也独立，一张表都未命中的概率为 $(1-p^k{)}^L$。完整扫描的候选召回率因此是

这些等式对单个固定对象对成立；不同记录是否命中不必相互独立。若该记录还满足核验谓词，则无预算截断时，候选命中就等价于最终报告这条记录。

常见的距离型假设给定 $r_1<r_2$ 与 $p_1>p_2$：距离至多 $r_1$ 的对象基础碰撞概率至少 $p_1$，距离大于 $r_2$ 的对象至多 $p_2$。那么每条固定近记录的遗漏率至多 $(1-p_1^k{)}^L$；对 $m$ 条预先固定的近记录要求全部报告，可用并集界给出遗漏概率至多 $m(1-p_1^k{)}^L$。对于归一化角度距离，$p=1-\theta /\pi$；对于 Jaccard 相似度，$p$ 就是 Jaccard 比。

令 $F$ 是距离大于 $r_2$ 的记录集合，$R_F$ 计它们在查询桶中的出现总次数，同一 ID 跨表重复也计入。期望线性性给出

不同远记录间的碰撞相关也不影响这个式子。它没有控制 $r_1$ 与 $r_2$ 之间的灰区，也没有控制大量真正的近记录。若所有记录和查询相同，每张表都包含全部 $n$ 条记录，出现次数就是 $nL$。

遍历预算也是输出合同的一部分 ​

参考允许非负整数预算 $B$，单位是读取的桶出现项，重复 ID 也消耗预算。先计算全部 $L$ 个查询键，用各桶长度求出总出现数 $R$，然后只扫描串接列表的前 $min(B,R)$ 项。没有预算参数时扫描全部。返回值同时包含：总出现数、实际扫描数、首次核验 ID、重复出现数、通过核验 ID，以及

• buckets_exhausted：本次选中的全部桶已读完，实际扫描数等于 $R$；
• budget_exhausted：仍有出现项未读，不能将这次结果当作完整候选集。

预算正好等于 $R$ 时属于前者。空记录表或空桶的 $R=0$，即使预算为零也已读完。buckets_exhausted 只说明命中的桶已尽，不代表整个数据库不存在漏掉的近记录。

截断后的报告概率通常不再等于 $f_{k,L}(p)$，因为记录可能碰撞了却排在截断之后。一个保守分解是

当 $B$ 为非负整数，由 $R\ge 0$ 和整数性可再界为 $(1-p^k{)}^L+\mathbb{E}[R]/(B+1)$，最后与 $1$ 取最小值。若只知道远记录的期望而不知道总 $R$，不能把 $\mathbb{E}[R_F]$ 偷换进这个式子。参考并不声称任意预算都有非平凡召回下界。

表不变量与成本核算 ​

构建处理完前 $t$ 条记录时，表 $j$ 的桶 $u$ 恰好按输入次序含有那些 $i\le t$ 且 $K_j(x_i)=u$ 的 ID。每条新记录在每张表恰好追加一次，归纳立即保持不变量。查询遍历前缀后，seen 恰为此前见过的不同 ID；核验列表是首次出现顺序，输出列表是其中谓词为真的子序列。逐项检查“新 ID / 旧 ID”两种情况，就证明了不重复输出、不错报与前缀预算语义。

设一次基础函数求值花 $H$，一次原值核验花 $D$，一次基础函数描述占 $S_h$ 个机器字，原始记录及 ID 存储占 $S_P$。在 ID、分量键为机器字且字典操作期望常数探测的模型下，复合键的计算、散列与比较还需要 $O(k)$，因此建表期望时间为

其中 $T_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}}$ 包括读取、校验、保存原值以及建立函数配置，空输入也支付配置成本。索引空间不能只说 $nL$：它包括 $Lk{S}_h$ 函数参数、$nL$ 个 ID 引用、至多 $nL$ 个长度为 $k$ 的元组键，以及表目录，合计

实际键数可能少于 $nL$，这是上界。稠密超平面有 $H=O(d),S_h=O(d)$；完整 MinHash 排列表需 $S_h=O(|U|)$，集合大小为 $s$ 时一次求值是 $O(s)$。这些参数成本不应藏进“每个 hash 常数时间”。

记本次实际读取的出现数为 $R^{\prime }\le R$，不同核验 ID 数为 $V\le min(n,R^{\prime })$。查询期望时间为

其中 $T_z$ 包含验证查询和阈值。另记规范查询值的副本大小为 $S_z$，单次核验的最大临时空间为 $W_{\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}}$；工作及返回空间是 $O(S_z+Lk+V+W_{\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}})$，与只读索引存储分开，不把桶列表重新复制出来。公开整数向量实现有 $S_z=O(d)$、$W_{\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}}=O(d)$，因为校验会形成元组副本；集合实现有 $S_z=O(|z|)$，交并集临时对象使 $W_{\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}}=O(\underset{i\text{ 已核验}}{max}|x_i|+|z|)$，无核验时该项取零。即使 $B=0$，参考也先计算全部查询键和桶长度，所以预算只限制出现项扫描与随后的核验。若 ID 是变长字符串、整数是任意精度，或字典遇到不利散列分布，对应位成本和探测退化需另计；上述期望界不是确定性的最坏保证。