21 球面 LSF 与过滤器#

整理日期：2026-10-16。
适用范围：球帽过滤器的几何概率、候选搜索与成本分析，以及球面 LSF 在两向量筛法中的作用。
前置笔记：15 高斯启发式与随机球面模型、19 筛法中的近邻搜索与分桶、20 角度 LSH 与多表搜索。

设当前维数为 $s\ge2$，数据库为非零向量池 $D=\{x_1,\ldots,x_N\}$，记归一化方向为 $u_i=x_i/\|x_i\|$。先固定数据库和非零查询向量 $x\notin D$，令 $u=x/\|x\|$。

本篇先用独立均匀随机的过滤器中心建立概率模型，再说明实际加速需要怎样的过滤器结构。原向量的长度与坐标仍保留，用于最终约化检查。

#1. 从哈希桶到球帽过滤器

第 20 篇的 LSH 用键指定向量在一张表中的桶。LSF 则直接规定“哪些向量通过某个过滤条件”。

对中心方向 $c\in S^{s-1}$ 和阈值 $\alpha\in(0,1)$，定义

通过条件的方向组成以 $c$ 为中心、半张角为 $\arccos\alpha$ 的球帽。一个过滤器只建立“通过”的桶；未通过的向量不会因为共同取值为 $0$ 而成为同桶候选。

使用多个过滤器时，一个向量可以进入多个桶，也可以一个都不进入。查询只访问它通过的过滤器对应的桶。

这是球面 LSF 的基本构造，见 Becker–Ducas–Gama–Laarhoven，SODA 2016，§3–4，PDF 第 4–5 页，下文简称 BDGL。

对任意固定方向 $u$，随机中心的单点通过率为第 15 篇的球帽概率：

固定 $\alpha$、令 $s\to\infty$ 时，

提高 $\alpha$ 会缩小球帽，从而减少单个桶的成员，也减少单个向量通过的过滤器。

#2. 共同通过率由两个球帽的交集决定

固定单位向量 $u,v$，夹角为 $\theta$，定义单侧共同通过率

把随机中心 $c$ 看作待选点，它必须同时位于以 $u$ 和 $v$ 为中心的两个球帽中。这个交集通常称为球楔（spherical wedge）。

因此，$q_s(\alpha,\theta)$ 依赖夹角，一般不等于 $p_s(\alpha)^2$。已知查询通过过滤器后，固定伙伴也通过的条件概率为

这个条件概率说明：查询挑选出的过滤器，已经带有关于查询方向的信息。

对于 $0<\theta<\pi$，同时满足两个内积约束所需的最小投影长度为

它可以从角平分线方向看出：两个约束都取等号时，最小范数投影为 $\frac{\alpha}{1+\cos\theta}(u+v)$，其长度正是 $\gamma$。

当 $\gamma<1$，且 $\alpha,\theta$ 固定时，共同通过率的指数主项为

其几何含义是：在 $u,v$ 所在平面中占用的投影长度至少为 $\gamma$，其余方向能够分配的平方长度最多为 $1-\gamma^2$。高维交集面积的指数由这个剩余量控制。推导见 BDGL，§2 的 Lemma 2.2 与 Appendix A，PDF 第 3、13–14 页。

需要保留公式的适用条件：

• 若 $\alpha\ge\cos(\theta/2)$，交集为空或只有零面积边界，故 $q_s(\alpha,\theta)=0$。
• 若 $\theta=0$，两个条件相同，直接有 $q_s(\alpha,0)=p_s(\alpha)$。
• 上述渐近式针对固定参数；有限维数或随维数变化的阈值，应另行计算或检查近似。

所以，过滤器不能无限缩小。若目标向量对的共同通过率已经为零，增加过滤器数量也无法覆盖它。

#3. 用对称球帽处理加法与减法

为同时寻找 $x-y$ 和 $x+y$ 的约化伙伴，沿用第 19 篇的对称过滤器：

数据库插入与查询都使用这个条件。 每个桶包含正、负两个球帽，一条向量在同一个桶中只存一次。

两个球帽在 $\alpha>0$ 时互不相交，因此单点通过率为

对夹角为 $\theta$ 的固定向量对，共同通过率为

这里有四种互斥的符号组合：同号的两种对应夹角 $\theta$，异号的两种对应夹角 $\pi-\theta$。中心取反使每组中的两个概率相同，因此得到上式。

若使用 $t$ 个独立均匀中心，该固定对至少被一个过滤器覆盖的概率为

单点通过率、共同通过率与多过滤器覆盖率是三个不同的量。桶成员数由 $p^\pm$ 决定，目标对覆盖由 $q^\pm(\theta)$ 决定，不能用前者直接替代后者。

#4. 索引、查询与计数

记查询方向 $u$ 通过的过滤器编号集合为

一个固定数据库上的基本流程如下：

BuildFilters(D, α, t):
    独立均匀采样中心 c_1, ..., c_t
    初始化空桶 B_1, ..., B_t

    对每条向量 x_j：
        u_j ← x_j / ||x_j||
        对 ℓ ∈ RelevantFilters(u_j)：
            将编号 j 加入 B_ℓ

RelevantFilters(u):
    返回 {ℓ : |〈u,c_ℓ〉| ≥ α}
    # 直接实现需要检查全部 t 个中心，不能省略这项成本

QueryCandidates(x):
    u ← x / ||x||
    Seen ← 空集合

    对 ℓ ∈ RelevantFilters(u)：
        对编号 j ∈ B_ℓ：
            如果 j 不在 Seen 中：
                将 j 加入 Seen
                输出 j

查询期间固定 $x$ 与 $D$，完整读取相关桶。输出后再按外层筛法的真实范数条件检查，并排除零结果；同桶本身不保证能够约化。

令 $F(u)=|I(u)|$，令 $M=\sum_\ell|B_\ell|$ 为全部桶的成员引用总数。对随机中心取期望：

这两个等式对任意固定数据库成立，不要求池内向量独立。

沿用第 20 篇的 $C_{\mathrm{raw}}$ 与 $C_{\mathrm{unique}}$，分别统计包含重复的成员访问和去重后的候选。若 $\theta_j=\theta(u,u_j)$，则

前式使用期望的线性性，后式还使用不同中心独立。不同候选之间不必独立；不同候选数也不等于实际池更新数。

全部桶同时驻留时，需要保存 $M$ 条成员引用，另计原向量、过滤器描述、桶管理与去重结构的空间。

#5. 真正的加速依赖高效定位过滤器

直接检查全部中心时，每个向量需要 $t$ 次内积。因此，第 4 节的朴素实现有

其中采用期望常数时间的编号去重与桶访问。

即使 $tp^\pm$ 很小，也不能把扫描全部中心的 $st$ 自动改成 $stp^\pm$。前者是寻找相关过滤器的成本，后者只反映相关过滤器的期望数量。

LSF 希望实现的是：以可控的附加开销，快速列出一个向量通过的过滤器，使定位成本主要随输出数量增长。

BDGL 为此使用随机乘积码组织中心：把空间分块，在各块中保存较小的码字集合，再利用组合结构和列表解码寻找相关中心。其分析同时处理解码成本与共同命中概率，见 BDGL，§3 的 Theorem 3.1 及其后的说明、§5 的 Lemma 5.1 与 Theorem 5.1。

换成结构化中心后，跨过滤器独立性通常不再成立。前面的 $1-(1-q)^t$ 不能直接照搬；覆盖率需要按该构造的相关性重新分析。

另一方面，若进一步假设数据库方向是独立球面均匀样本，且与查询、过滤器独立，则有

这是对随机数据库与中心共同平均后的结果：固定中心后，数据库成员通过的概率为 $p^\pm$，查询选中该中心的概率也为 $p^\pm$。

它已经平均了数据库的角度分布，不能据此将每个固定目标对的 $q^\pm(\theta)$ 都设为 $(p^\pm)^2$。随机球面输入下的成本关系可对照 Laarhoven《Tradeoffs for nearest neighbors on the sphere》，arXiv:1511.07527v2，Appendix B.1，PDF 第 15 页。

#6. 一个经典参数选择及其指数

下面只保留维数的指数主项，并暂用单侧球帽记号。正负对称会引入常数因子，但不改变本节的指数。

采用第 15 篇的启发式池规模

并将输入方向建模为独立球面均匀样本，以等长约化的 $60^\circ$ 边界估算目标对命中率。真实约化仍需严格的长度检查，边界本身不产生严格缩短。

取 $\alpha=1/2$，则

为了以常数概率覆盖一个固定目标对，独立过滤器模型中取 $t=\Theta(1/q)$，于是

再假设有满足所需覆盖性质的高效过滤器定位方法，其附加开销不改变指数。建立索引并进行约 $N$ 次查询时，成员插入、相关过滤器定位与桶成员检查的期望成本，在指数尺度上写为：

因为 $Np=2^{o(s)}$，两项具有相同的指数，得到

全部桶驻留时，成员引用数的期望 $Ntp$ 也具有这一指数。这个计算解释了 BDGL 对称参数选择中的经典时间、空间尺度，参见 BDGL，§7，Theorem 7.1 及 $\alpha=\beta=1/2$ 的参数讨论，PDF 第 10–11 页。

高效定位是实质条件：如果仍逐个检查全部过滤器，同样参数下仅建桶就需要

量级的运算，无法得到上面的时间指数。

本节是随机球面与高效定位假设下的搜索成本估计。完整筛法的成功率、轮数和向量分布还需要相应的启发式分析；逐桶处理能否降低内存，也取决于具体批量流程，不能直接套用于任意动态筛法。

#7. 非对称过滤与多层分桶

插入数据库与查询不必使用相同阈值。写成单侧形式，可以分别定义

此时，固定 $t$ 后：

• $\alpha_{\mathrm{ins}}$ 控制桶成员数与索引引用数，其期望分别为 $Np_s(\alpha_{\mathrm{ins}})$ 与 $Ntp_s(\alpha_{\mathrm{ins}})$。
• $\alpha_{\mathrm{qry}}$ 控制一次查询访问的过滤器数量，其期望为 $tp_s(\alpha_{\mathrm{qry}})$。
• 目标对的共同通过率由两个不同大小的球帽交集决定，仍需单独计算。

提高任一阈值都会使对应筛选更严格，也可能要求增加 $t$ 才能维持目标覆盖率。因此，时间与空间权衡应在相同搜索质量下比较。非对称阈值的定义及分析见 Laarhoven，arXiv:1511.07527v2，§3 开头、§3.3 与 §4。

继续进入 BGJ 多层分桶时，需要保留本篇的三个量：单点通过率、有效对共同通过率，以及寻找相关桶的成本。

多层筛选还会引入条件分布：进入上层桶后，方向与夹角已受到限制，下层概率不能直接沿用未筛选的球面模型。下一篇可以据此展开 BGJ 递归分桶，说明每层如何改变候选规模、配对覆盖与重复检查。

#引用此笔记

• 00 概览与阅读路线
• 22 BGJ 递归分桶与多层筛选
• 23 多层分桶的参数选择与优化