# 21 球面 LSF 与过滤器

整理日期：2026-10-16。  
适用范围：球帽过滤器的几何概率、候选搜索与成本分析，以及球面 LSF 在两向量筛法中的作用。  
前置笔记：[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)、[19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)、[20 角度 LSH 与多表搜索](/knowledge/angular-lsh-and-multiple-tables/)。

设当前维数为 $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)$，定义

$$
f_{c,\alpha}(u)
=\mathbf 1\{\langle u,c\rangle\ge\alpha\}.
$$

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

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

这是球面 LSF 的基本构造，见 [Becker–Ducas–Gama–Laarhoven，SODA 2016，§3–4，PDF 第 4–5 页](https://ir.cwi.nl/pub/23692/23692.pdf)，下文简称 BDGL。

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

$$
p_s(\alpha)
=\Pr_c[\langle u,c\rangle\ge\alpha].
$$

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

$$
p_s(\alpha)
=2^{\,\frac s2\log_2(1-\alpha^2)+O(\log s)}.
$$

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

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

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

$$
q_s(\alpha,\theta)
=
\Pr_c[
\langle u,c\rangle\ge\alpha,\
\langle v,c\rangle\ge\alpha
].
$$

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

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

$$
\Pr[f_{c,\alpha}(v)=1\mid f_{c,\alpha}(u)=1]
=\frac{q_s(\alpha,\theta)}{p_s(\alpha)}.
$$

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

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

$$
\gamma
=\frac{\alpha}{\cos(\theta/2)},
\qquad
\gamma^2=\frac{2\alpha^2}{1+\cos\theta}.
$$

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

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

$$
\boxed{
q_s(\alpha,\theta)
=
2^{\,\frac s2
\log_2\!\left(1-\frac{2\alpha^2}{1+\cos\theta}\right)
+O(\log s)}.
}
$$

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

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

- 若 $\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 篇的对称过滤器：

$$
f^\pm_{c,\alpha}(u)
=\mathbf 1\{|\langle u,c\rangle|\ge\alpha\}.
$$

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

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

$$
p^\pm=2p_s(\alpha).
$$

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

$$
\boxed{
q^\pm(\theta)
=
2q_s(\alpha,\theta)
+
2q_s(\alpha,\pi-\theta).
}
$$

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

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

$$
P^\pm_t(\theta)
=1-\left(1-q^\pm(\theta)\right)^t.
$$

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

## 4. 索引、查询与计数

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

$$
I(u)=\{\ell:|\langle u,c_\ell\rangle|\ge\alpha\}.
$$

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

~~~text
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|$ 为全部桶的成员引用总数。对随机中心取期望：

$$
\mathbb E[F(u)]=tp^\pm,
\qquad
\mathbb E[M]=Ntp^\pm.
$$

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

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

$$
\mathbb E[C_{\mathrm{raw}}]
=t\sum_{j=1}^N q^\pm(\theta_j),
$$

$$
\mathbb E[C_{\mathrm{unique}}]
=
\sum_{j=1}^N
\left[1-(1-q^\pm(\theta_j))^t\right].
$$

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

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

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

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

$$
T_{\mathrm{build}}=O(sNt),
$$

$$
T_{\mathrm{query}}
=
O\!\left(
st+C_{\mathrm{raw}}+sC_{\mathrm{unique}}
\right),
$$

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

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

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

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

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

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

$$
\mathbb E_{D,c}[C_{\mathrm{raw}}]
=Nt(p^\pm)^2.
$$

这是对随机数据库与中心共同平均后的结果：固定中心后，数据库成员通过的概率为 $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 页](https://arxiv.org/pdf/1511.07527v2)。

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

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

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

$$
N=(4/3)^{s/2+o(s)},
$$

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

取 $\alpha=1/2$，则

$$
p=p_s(1/2)
=(3/4)^{s/2+o(s)},
\qquad
q=q_s(1/2,\pi/3)
=(2/3)^{s/2+o(s)}.
$$

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

$$
t=(3/2)^{s/2+o(s)}.
$$

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

$$
T_{\mathrm{model}}
=
2^{o(s)}
\left(
Ntp+N^2tp^2
\right).
$$

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

$$
\boxed{
T_{\mathrm{model}}
=
(3/2)^{s/2+o(s)}
=
2^{\,\frac12\log_2(3/2)\,s+o(s)},
\qquad
\frac12\log_2(3/2)\approx0.2925.
}
$$

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

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

$$
sNt=2^{s/2+o(s)}
$$

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

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

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

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

$$
B_\ell
=\{j:\langle u_j,c_\ell\rangle\ge\alpha_{\mathrm{ins}}\},
\qquad
I_{\mathrm{qry}}(u)
=\{\ell:\langle u,c_\ell\rangle\ge\alpha_{\mathrm{qry}}\}.
$$

此时，固定 $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](https://arxiv.org/pdf/1511.07527v2)。

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

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

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)
- [23 多层分桶的参数选择与优化](/knowledge/multilevel-bucketing-optimization/)