整理日期：2026-10-16。
适用范围：欧氏格两向量筛法中的伙伴搜索、分桶候选生成，以及检查成本和有效配对覆盖的基本模型。
前置笔记：15 高斯启发式与随机球面模型、17 筛法的基本框架与两向量约化、18 Nguyen–Vidick、ListSieve 与 GaussSieve。
设当前筛法维数为 \(s\ge2\)，待搜索的非零格向量池为 \(D=\{x_1,\ldots,x_N\}\)。本篇先固定一轮中的输入池，不预设它已经两两约化。
1. 筛法需要怎样的近邻搜索#
第 18 篇中的基础算法需要反复寻找能够产生较短结果的向量。搜索任务可以分为两种：
- 单个候选的伙伴搜索。 给定 \(x\)，在当前池中寻找满足约化条件的 \(y\)；找到后可能更新 \(x\) 并继续搜索。
- 批量配对搜索。 在整个池中寻找许多有效向量对，供下一轮筛选或数据库更新使用。
BGJ 将后一类任务表述为：给定单位向量列表和角度阈值，寻找夹角满足阈值的向量对。参见 Becker–Gama–Joux，ePrint 2015/522，摘要中的固定半径近邻问题。
以下批量模型采用“缩短两条向量中较长者”的判据。令
则有效对满足
等长情形下，这对应第 15 篇的 \(|\cos\theta|>1/2\)，并排除产生零向量的情形。长度不同时，需要保留真实范数；归一化方向只用于组织搜索。
这里通常只需要找到符合长度条件的伙伴，不必找到有限池中距离最小的元素。搜索范围也是当前池中的有限个向量；CVP 的搜索范围则是整个格。
嵌入具体算法时，仍应使用它原有的约化方向和目标长度。例如，用 \(y\) 缩短指定的 \(x\)，与只要求缩短两者中的较长者，是不同的任务。
2. 用桶生成候选#
分桶先把可能形成有效对的向量放到共同的小集合中，再检查这些集合内部的向量对。
令
考虑一个简单的对称球帽模型：选择中心方向 \(c_\ell\in S^{s-1}\) 和阈值 \(0<\alpha<1\)，定义
它包含以 \(c_\ell\) 和 \(-c_\ell\) 为中心的两个球帽，用绝对值同时照顾加法与减法方向。桶中存储原向量的编号，长度和坐标仍保留在 \(D\) 中。
单侧球帽过滤 \(\langle u,c\rangle\ge\alpha\) 是球面 LSF 的基本构造；本篇在此基础上使用对称的两个球帽。参见 Becker–Ducas–Gama–Laarhoven，SODA 2016，§4，PDF 第 5 页。
需要区分三个性质：
- 桶可以重叠，一条向量可以进入多个桶。
- 同桶只意味着成为待检查的候选，不保证满足约化条件。
- 有效对也可能没有进入任何共同的桶，因此需要分析漏检概率。
提高 \(\alpha\) 会缩小桶，但也可能降低有效对共同入桶的概率。分桶参数要同时考虑检查成本与搜索覆盖。
3. 一个固定输入池的搜索流程#
下面的伪代码使用 \(t\) 个独立、均匀随机的中心，展示一次批量搜索。它允许跨桶重复检查，也允许重复输出：
BucketSearch(D, α, t):
固定本轮的 D，计算各向量的范数与归一化方向
重复 t 次：
c ← 在单位球面上独立均匀采样
B ← {i : |〈u_i,c〉| ≥ α}
对 B 中每个无序对 i < j：
σ ← 1（若 〈x_i,x_j〉 ≥ 0），否则 −1
w ← x_i − σ·x_j
如果 0 < ||w|| < max(||x_i||, ||x_j||)：
输出 (i, j, w) # 可以流式处理
释放本桶符号选择使 \(w\) 在 \(x_i-x_j\) 和 \(x_i+x_j\) 中取较短者。输出的是候选及其来源，外层算法再决定去重、接纳和替换规则。
这个流程仅描述搜索阶段。它没有规定初始采样、完整筛法的停止条件，也没有凭分桶本身保证找到最短向量。
4. 检查次数与有效对覆盖#
记第 \(\ell\) 个桶的大小为 \(b_\ell=|B_\ell|\)。如果每个桶内部都完整枚举无序对，且没有跨桶去重，则检查次数为
同一对向量在三个桶中出现，就贡献三次检查。因此，平均桶大小不足以确定 \(C\)；在总入桶次数固定时，桶大小越不均衡，检查次数越多。
对固定源向量对 \((i,j)\)，定义共同入桶次数
于是
再令 \(E\) 为固定输入池中所有有效无序对的集合，则：
其中，\(H\) 是包含重复的有效对命中次数，\(U\) 是实际覆盖的不同有效源向量对数。对本流程，\(C-H\) 是未通过约化检查的次数。
\(U\) 仍不等于不同新向量的数量：不同源向量对可能产生相同结果，结果也可能已在池中。实际池更新还取决于接纳规则。
以上等式直接来自固定输入池、完整桶内枚举的计数定义。若提前停止、跨桶去重或在搜索中修改输入池，需要按实际流程重新计数。
5. 从入桶概率到覆盖概率#
下面的概率公式都针对第 3 节的理想化随机中心模型。
对任意固定单位向量 \(u\)，令
其中 \(p_s(\alpha)\) 是第 15 篇定义的单侧球帽概率。由旋转对称性，\(p\) 不依赖 \(u\) 的方向，因此对任意固定输入池都有
这个期望不要求池内向量相互独立。
但两个固定向量共同入桶的概率是
\(q_{ij}\) 取决于两条向量的夹角，一般不等于 \(p^2\)。单侧版本由两个球帽交集的相对面积描述；双侧版本还需要计入对应的符号方向。球帽交集与共同过滤概率的关系见 BDGL，§2 的球楔定义与 §4，PDF 第 3、5 页。
由期望的线性性，检查次数满足
固定一对 \((i,j)\)，由于不同桶中心独立采样，它至少共同入桶一次的概率为
因此，不同有效源向量对的预期覆盖数为
覆盖公式使用了同一对向量在不同桶中的命中事件独立这一条件，不要求不同源向量对之间独立。检查次数的期望只使用线性性。使用结构化、相关或自适应选择的桶时，需要重新核对覆盖公式。
若希望某个固定有效对的漏检概率至多为 \(\delta\in(0,1)\)，且 \(q_{ij}>0\)，则需要
这是单个固定对的要求；覆盖全部有效对还要控制整体失败概率。若某类有效对的 \(q_{ij}=0\)，增加桶数也无法找回它们。
只有进一步把输入方向建模为独立球面均匀样本，并让中心与输入独立时，才可对输入与中心共同取期望，得到
这个随机输入平均式不能直接替代实际固定池中的 \(\sum q_{ij}\)，尤其不能把有效对的共同入桶概率设成 \(p^2\)。桶内筛选和后续多层条件还会改变分布。
6. 分桶成本需要包含建桶#
对第 3 节的直接实现，每个中心都扫描全部 \(N\) 条向量。按 \(s\) 维内积的运算量计，
完整流程还要计入候选去重、池更新和访存成本。检查次数变少，并不自动意味着总时间下降；寻找相关桶和生成桶成员本身也可能很昂贵。
内存同样取决于处理顺序：若逐桶处理并释放，桶成员引用的峰值为 \(\max_\ell b_\ell\)；若同时保存全部桶，则为 \(\sum_\ell b_\ell\)。原向量、中心、索引和候选缓冲的存储另计。
BDGL 的 LSF 分析明确把“高效找到一个向量所属的过滤器”作为关键条件，并进一步构造相应的结构化方法。参见 BDGL，§3 的 Theorem 3.1 及其后的说明、§5。
7. LSH、LSF 与具体筛法的衔接#
LSH 通过哈希值组织桶。 在一张标准哈希表中，\(h(u)\) 指定向量所属的一个桶；查询检查相同键对应的候选，多张表提供多次相遇机会。
以 Charikar 的随机超平面哈希为例，随机选择单位方向 \(a\)，令
若两方向夹角为 \(\theta\)，则
夹角越小，同键概率越大；同键仍不保证满足筛法长度条件。构造与公式见 Laarhoven，CRYPTO 2015，ePrint 2014/744 的 23 页版，§2.5，式 (3)–(4)，PDF 第 6 页。
用于同时处理加法与减法时，需要查询正负两个方向，或采用等价的符号对称设计。
LSF 通过过滤条件组织桶。 每个过滤器判断一个向量是否通过；一个向量可以通过多个过滤器，也可能一个都不通过。第 2 节的球帽桶提供了一个具体模型。两者的区别在于候选集合如何生成，不能仅由程序是否使用哈希表来判断。参见 BDGL，§3，PDF 第 4–5 页。
将这些搜索方法接入筛法，还要维护原算法的状态：
- 批量流程可以固定本轮输入，收集候选后统一更新。
- 动态流程中，向量改变后，需要同步更新对应索引；再次约化也需要根据新向量重新搜索。
- 概率搜索没有找到伙伴，只表示本次未命中，不能据此认证“两两约化完成”，也不能直接继承完整扫描时的不变量。
角度 LSH 接入 NV 类筛法和 GaussSieve 的具体方式，可参见 Laarhoven，§3 与 §5，并对照第 18 篇中的更新规则。
后续先展开角度 LSH 的多位组合与多表搜索，再进入球面 LSF 和 BGJ 递归分桶。比较具体方法时，继续沿用本篇的四类量：建桶成本、向量对检查次数、不同有效对覆盖数，以及实际池更新。