整理日期：2026-10-16。
适用范围：BGJ 的递归近邻搜索框架、球帽版本的多层分桶，以及条件分布、配对覆盖和时间空间成本。
前置笔记：19 筛法中的近邻搜索与分桶、20 角度 LSH 与多表搜索、21 球面 LSF 与过滤器。
设当前筛法维数为 \(s\)，固定一轮输入池 \(D=\{x_1,\ldots,x_N\}\)，所有向量非零，记 \(u_i=x_i/\|x_i\|\)。本篇继续研究两向量约化中的批量伙伴搜索。
1. BGJ 递归地缩小搜索列表#
单层分桶把整个池分成若干重叠的小桶，再枚举桶内向量对。BGJ 继续对桶进行过滤，直到列表足够小，再做两两检查。
递归过程中改变的是搜索列表；原格向量及其所在的 \(s\) 维空间保持不变。一个向量可以进入多个子桶，同一源向量对也可能沿不同路径到达多个叶子。
需要区分原始过滤器与后续球帽版本：
BGJ15 原始构造使用多个随机超平面的符号计数。取独立随机方向 \(a_1,\ldots,a_r\)，参数 \(\delta\in(0,1)\)，过滤条件为
这里保留符号计数偏向一侧的向量。原论文在过滤后的子列表上递归，列表足够小时转为直接枚举。参见 Becker–Gama–Joux，ePrint 2015/522，§3，过滤器定义与 Algorithm 3。
球帽版本沿用递归框架，将每层过滤条件换为
$$ f^\pm_{c,\alpha}(u)#
\mathbf 1{|\langle u,c\rangle|\ge\alpha}. $$
Zhao–Ding–Yang 将使用一、二、三层过滤的版本分别称为 bgj1、bgj2、bgj3。这里的数字表示过滤层数，最终仍检查两条向量的和或差。参见 《Sieving with Streaming Memory Access》，§3.2，Algorithms 2–3，所链接 PDF 第 6–7 页。
下文主要用球帽版本说明多层分桶，最后再回到 BGJ15 的经典复杂度。
2. 一个固定输入池的递归流程#
设最多使用 \(k\) 层过滤。第 \(\ell\) 层的阈值为 \(\alpha_\ell\)，每个父桶尝试 \(t_\ell\) 个子桶，\(\ell=0,\ldots,k-1\)；\(b_{\min}\) 是转为直接枚举的大小阈值。
本篇的 \(t_\ell\) 均指每个父桶的分支数。若完整展开且不提前结束，第 \(\ell\) 次过滤后生成的桶总数为 \(\prod_{h=0}^{\ell}t_h\)。
下面的流程逐个生成、处理并释放子桶。桶内只保存原向量编号，输入池在本轮搜索中保持不变：
Search(I, ℓ): # 初始调用 Search({1,...,N}, 0)
如果 |I| < 2：
返回
如果 ℓ = k 或 |I| ≤ b_min：
对 I 中每个无序对 i < j：
σ ← 1（若 〈x_i,x_j〉 ≥ 0），否则 −1
w ← x_i − σ·x_j
如果 0 < ||w|| < max(||x_i||, ||x_j||)：
输出 (i, j, w)
返回
重复 t_ℓ 次：
c ← 在原 s 维单位球面上独立均匀采样
J ← {i ∈ I : |〈u_i,c〉| ≥ α_ℓ}
Search(J, ℓ + 1)
释放 J此处沿用第 19 篇“缩短两者中较长者”的判据。接入具体筛法时，可以换成外层规定的目标长度和接纳规则。
这个固定输入版本允许跨桶重复检查和输出，便于分析。实际实现可能在收集一批候选后更新数据库；更新后的搜索应视为新状态，不能继续套用旧池中的固定源对统计。
3. 桶内的条件分布#
沿一条路径经历若干过滤后，桶对应的方向区域为
$$ A_\ell#
\bigcap_{h=0}^{\ell-1} {u\in S^{s-1}:|\langle u,c_h\rangle|\ge\alpha_h}. $$
它是多个双侧球帽的交集。不同路径的中心不同，对应的区域也不同。
在球面均匀输入模型下，固定这些过滤器后，保留下来的方向服从限制在 \(A_\ell\) 内的分布。若下一过滤区域为 \(F\)，且 \(\mu(A_\ell)>0\)，则
$$ \Pr[U\in F\mid U\in A_\ell]#
\frac{\mu(A_\ell\cap F)}{\mu(A_\ell)}, $$
其中 \(\mu\) 是球面面积测度。这个条件比例通常不能用 \(\mu(F)/\mu(S^{s-1})\) 替代。
筛选没有改变一对给定向量的夹角，改变的是“从桶内抽取一对向量”时的夹角分布。
例如，仅看一个单侧球帽，将两条单位向量写成
其中 \(a,b\in[\alpha,1)\)，\(\xi,\eta\) 是 \(c^\perp\) 中的单位向量。由内积展开，
$$ \langle u,v\rangle#
ab+\sqrt{(1-a^2)(1-b^2)},\langle\xi,\eta\rangle. $$
等长向量的减法约化条件 \(\langle u,v\rangle>1/2\) 因而等价于
$$ \langle\xi,\eta\rangle
\frac{1/2-ab}{\sqrt{(1-a^2)(1-b^2)}}. $$
共同的中心分量影响了剩余方向需要满足的条件。只知道桶大小，无法完整描述桶内的配对几何；多层后还需要考虑多个约束的共同作用。这些等式是直接的几何分解，不要求采用某个启发式分布。
同时，要分清随机性来自哪里：若固定当前向量，再独立均匀抽取一个全空间中心，则无论它此前怎样入桶，单点通过率仍为 \(2p_s(\alpha)\)；固定向量对的共同通过率也仍由其原夹角决定。
因此，“桶内分布改变”不意味着所有单次过滤公式都失效。需要重新分析的是桶内随机向量对的平均行为，以及依赖父桶选择中心、限制中心方向等具体方案。
4. 重复命中与整棵树的覆盖#
设实际形成的叶子集合为 \(\mathcal L\)，叶子 \(\lambda\) 中的编号集合为 \(I_\lambda\)。完整枚举叶子内部无序对时，
$$ C#
\sum_{\lambda\in\mathcal L}\binom{|I_\lambda|}{2}#
\sum_{i<j}m_{ij}, \qquad m_{ij}#
\sum_{\lambda\in\mathcal L} \mathbf 1{i,j\in I_\lambda}. $$
沿用第 19 篇，记 \(E\) 为固定输入池中的有效源对集合，则
\(H\) 统计包含重复的有效命中，\(U\) 统计不同有效源对。增加叶子数量可能同时增加覆盖与重复；不同源对仍可能产生相同的新向量。
尤其需要注意：共享父桶的叶子，其命中事件通常不独立。
考虑一个恰好两层、没有提前终止的模型。每个节点都使用新的独立均匀中心，固定一对夹角为 \(\theta\) 的向量，令 \(q_0,q_1\) 分别为两层的共同通过率。根节点尝试 \(t_0\) 个父桶，每个父桶尝试 \(t_1\) 个子桶。
该源对在叶子中的期望出现次数为
$$ \mathbb E[m_{ij}]#
t_0t_1q_0q_1. $$
但至少命中一个叶子的概率是
$$ \boxed{ P_{\mathrm{cov}}#
1- \left( 1-q_0\left[1-(1-q_1)^{t_1}\right] \right)^{t_0}. } $$
推导只需两步：先通过一个父桶，概率为 \(q_0\)；在此前提下，至少通过它的一个子桶，概率为 \(1-(1-q_1)^{t_1}\)。最后对独立的顶层分支计算至少一次成功。
不能把它一般地写成 \(1-(1-q_0q_1)^{t_0t_1}\)，因为同一父桶下的 \(t_1\) 条路径共享第一次过滤。增加这些子桶，无法补回在该父桶入口已经丢失的源对。
这个公式由上述两层模型直接推得。若子层中心依赖父桶内容，或采用结构化、相关的中心，需要使用相应的条件概率重新计算。
5. 建桶、叶子检查与驻留空间#
记实际递归树的内部节点集合为 \(\mathcal V\)。对节点 \(v\)，父桶大小为 \(b_v\)，尝试的子桶数为 \(t_v\)。
若每个子桶都直接扫描父桶，并用 \(s\) 维内积检查成员，主要算术成本为
$$ T_{\mathrm{filter}}#
O!\left(s\sum_{v\in\mathcal V}t_vb_v\right), \qquad T_{\mathrm{pair}}#
O!\left(s\sum_{\lambda\in\mathcal L} \binom{|I_\lambda|}{2}\right). $$
前式统计每层建桶，后式统计叶子检查。候选去重、数据库更新与数据移动还需另计。
增加一层是否有利，取决于：新增的过滤成本，能否由减少的两两检查成本补偿，并维持所需覆盖。 桶变小本身不足以判断总时间是否下降。
桶大小的波动也会影响成本。对随机桶大小 \(B\)，
$$ \mathbb E!\left[\binom B2\right]#
\frac{(\mathbb E B)^2-\mathbb E B+\operatorname{Var}(B)}{2}. $$
只用平均桶大小代入平方，会漏掉方差贡献。
空间成本取决于处理顺序。对第 2 节的深度优先流程，临时成员引用主要来自当前递归路径上的桶：
$$ M_{\mathrm{idx}}#
O!\left( \max_{\text{执行时刻}} \sum_{I\in\text{当前路径}}|I| \right). $$
若桶沿路径按固定比例收缩，这部分为 \(O(N)\)；原始向量坐标另需 \(O(sN)\) 空间，中心、递归状态和候选缓冲也应计入。一次保存全部兄弟桶，或保存全局已检查源对集合，会改变这个空间模型。
实际实现还可以把若干中心组成一批：顺序读取父桶中的向量，一次完成多个过滤测试。内积测试数量没有因此消失，但读取的数据可以被复用，小桶也更容易放入较快的存储层。流式访存与分层桶大小的关系可参见 Zhao–Ding–Yang，§4.2，所链接 PDF 第 9–10 页。
6. 原始 BGJ 的复杂度从何而来#
先抽象出两个概率：
- \(p\)：固定向量通过一个随机过滤器的概率。
- \(q\)：处于目标夹角的固定向量对共同通过该过滤器的概率。
用典型子桶大小 \(pb\) 代替实际大小，忽略成功率放大因子，并取约 \(1/q\) 个子桶，可以写出示意递推
其中 \(a_f\) 是一次单向量过滤的成本，包含其内积计算。
若递归项表现为 \(b^d\)，代入得到
当 \(q>p^2\) 时，\(d<2\)：有效对共同通过的概率，高于两个独立通过率的乘积，因而有机会获得次二次搜索。
这个推导解释了概率比如何进入复杂度。它还依赖典型桶大小、递归深度与成功率控制，不能单凭 \(p,q\) 就断言任意多层实现的运行时间。
BGJ15 在其列表大小启发式与渐近参数选择下，将 \(60^\circ\) 目标角对应的列表规模指数推向 \(d=3/2\)。配合经典两向量筛法的列表尺度，
相应时间、空间尺度为
它们的二进制指数系数分别为 \(0.311278\ldots\) 和 \(0.207518\ldots\)。参见 BGJ15，§3 的 Heuristic 1、§3.1 的递推式与 Theorem 1、§3.2 的 Theorem 2。
这些是原论文模型中的启发式渐近尺度。具体的 bgj1、bgj2、bgj3 需要根据过滤器、层数、参数与实际桶分布单独分析；也不能把第 21 篇 BDGL 的时间指数直接移植到任意球帽递归实现。
7. 多层参数怎样比较#
需要联合选择的参数包括：层数 \(k\)、各层阈值 \(\alpha_\ell\)、每个父桶的分支数 \(t_\ell\)、直接枚举阈值 \(b_{\min}\)，以及同时处理的桶批量。
提高阈值通常减少成员，却也降低目标对的共同通过率；增加分支提高覆盖，同时增加建桶与重复检查。增加层数还会改变条件几何和数据访问方式，因此适合在相同搜索质量下比较完整成本。
对固定输入池，可以先按三个方面记录：
- 桶的规模： 各层桶大小分布、成员引用总数，以及叶子内部的检查次数。
- 搜索的效果： 含重复的有效命中 \(H\)、不同有效源对 \(U\)，再单独记录不同候选向量与实际接纳数量。
- 实际的成本： 过滤、配对检查、去重与更新的时间，以及峰值内存和主要数据移动量。
若无法得到全部有效对作为覆盖率分母，可以使用可完整枚举的小规模实例，或明确标注抽样估计；不能把“命中次数更多”直接解释为“覆盖更好”。
从概率模型进入实现时，还要核对中心的来源。例如，G6K 的 bgj1 从当前数据库中选择中心，并利用中心与桶成员之间的约化机会；这与本篇独立球面中心的固定输入模型有所区别。参见 G6K，kernel/bgj1_sieve.cpp 的算法说明，检索于 2026-10-16。
本篇建立的基线是：递归分桶流程、条件概率、源对覆盖，以及完整成本计数。后续阅读论文时，可以据此分别整理多层参数优化、重复源对处理和平台实现带来的增量。