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