整理日期：2026-10-16。
适用范围：随机超平面角度 LSH 的候选生成、多表覆盖、参数选择，以及与两向量筛法的衔接。
前置笔记：15 高斯启发式与随机球面模型、18 Nguyen–Vidick、ListSieve 与 GaussSieve、19 筛法中的近邻搜索与分桶。
沿用第 19 篇的记号：当前维数为 \(s\ge2\)，非零向量池为 \(D=\{x_1,\ldots,x_N\}\)。本篇先研究固定数据库 \(D\) 与固定非零查询向量 \(x\notin D\)，并假设它们与随机哈希函数的选择独立。
核心思路是：用多个随机超平面的符号组成桶键，再用多张独立的表提高近邻命中率。桶只负责产生候选，是否能够约化仍由真实长度决定。
1. 随机超平面为什么对角度敏感#
对非零向量 \(x,y\)，记其夹角为
从单位球面均匀采样法向量 \(a\)，定义一位哈希
超平面 \(a^\perp\) 把空间分成两侧，同侧向量取得相同的位。
在包含 \(x,y\) 的二维平面内，随机分界线将两者分开的概率为 \(\theta/\pi\)，所以
这是 Charikar 的随机超平面构造。本篇按 Laarhoven，CRYPTO 2015，ePrint 2014/744 的 23 页版，§2.5，式 (2)–(4)，PDF 第 6 页 核对。
因此，夹角越小，同键概率越大。例如，\(60^\circ\) 时为 \(2/3\)，\(90^\circ\) 时为 \(1/2\)。
该公式对任意预先固定的非零向量对成立，不要求数据库方向均匀。哈希值只依赖方向，计算符号时不必显式归一化；原向量的长度仍须保留。
2. 多位组合与多表放大#
设每张表使用 \(k\ge1\) 位，共建立 \(t\ge1\) 张表。所有法向量 \(a_{\ell,r}\) 相互独立，定义第 \(\ell\) 张表的键
$$ g_\ell(x)#
\bigl(h_{a_{\ell,1}}(x),\ldots,h_{a_{\ell,k}}(x)\bigr) \in{0,1}^k. $$
数据库中的向量 \(y\) 存入桶 \(T_\ell[g_\ell(y)]\)。
同一张表要求全部 \(k\) 位相同。 固定夹角为 \(\theta\) 的向量对，其单表碰撞概率为
多表搜索只要求至少一张表命中。 查询每张表的同键桶后，覆盖概率为
这分别是 AND 组合与 OR 放大的作用。多表索引的基本构造也可参见 Har-Peled–Indyk–Motwani，Theory of Computing 2012，§3.2，PDF 第 17–18 页。
两个参数的作用不同：
- 增大 \(k\)：近点和远点都更难碰撞，但远点的概率下降得更快，候选更少。
- 增大 \(t\)：提高覆盖率，同时增加建表、查询和索引存储成本。
若某个固定目标的单表命中率为 \(q\in(0,1)\)，希望漏检概率不超过 \(\delta\)，则
这是对一个固定目标的要求。它既不表示命中次数等于不同候选数，也不直接保证全部有效对都被覆盖。
3. 筛法为什么要查询正负两个方向#
两向量约化需要同时考虑 \(x-y\) 与 \(x+y\)。若只查 \(g_\ell(x)\)，就偏向寻找与 \(x\) 同向的伙伴，容易遗漏接近 \(-x\) 的伙伴。
一种直接设计是：每条数据库向量在每张表中只存一次；查询时读取
在连续随机模型中，固定非零向量落在超平面上的概率为零，因而几乎必然有
其中横线表示逐位取反。
对固定的 \(x,y\)，记 \(\theta=\theta(x,y)\)。由于 \(k\ge1\)，这两个键不同；\(y\) 在同一张表中不能同时落入两个查询桶。因此双向单表命中率是两个互斥事件的概率之和：
$$ \boxed{ q_k^\pm(\theta)#
\left(1-\frac{\theta}{\pi}\right)^k + \left(\frac{\theta}{\pi}\right)^k. } $$
相应的多表覆盖概率为
$$ P_{k,t}^\pm(\theta)#
1-\left(1-q_k^\pm(\theta)\right)^t. $$
以上双向公式由两个查询键直接推得。同一表内的两次查桶不能当作两次独立随机试验，也不能一般地把单向概率乘以 \(2\)。
一个简单检查是：\(k=1\) 时，\(q_1^\pm(\theta)=1\)。此时正负查询恰好读取一张表的全部两个桶，等于扫描整个数据库，没有过滤作用。
4. 固定数据库上的候选查询#
下面的流程完整读取所有指定桶，并按向量编号去重。查询过程中不改变 \(x\) 或 \(D\)，也不提前停止。
BuildIndex(D, k, t):
对每张表 ℓ = 1, ..., t：
独立采样 k 个随机超平面，确定键函数 g_ℓ
T_ℓ ← 空的桶字典
对每条向量 x_j ∈ D：
将编号 j 加入 T_ℓ[g_ℓ(x_j)]
返回所有键函数和哈希表
QueryCandidates(x):
Seen ← 空集合
对每张表 ℓ = 1, ..., t：
key ← g_ℓ(x)
对 b ∈ {key, 逐位取反(key)}：
对编号 j ∈ T_ℓ[b]： # 不存在的桶视为空
如果 j 不在 Seen 中：
将 j 加入 Seen
输出 j输出编号后，再按外层算法的约化规则检查。
例如，若任务是用 \(y=x_j\) 缩短指定的 \(x\)，可以令
并检查
这与第 19 篇中“缩短两者的较长者”采用的判据不同。若外层算法使用目标半径、双向约化或其他接纳规则，应保留对应条件。
5. 重复访问、不同候选与实际成本#
记 \(\theta_j=\theta(x,x_j)\)，并令
对第 4 节的完整查询，定义：
- \(C_{\mathrm{raw}}\)：从各表读取的桶成员总数，包含跨表重复。
- \(C_{\mathrm{unique}}\)：去重后的不同候选编号数。
对随机索引取期望，有
第一式只用期望的线性性；第二式还使用同一向量对在不同表中的命中事件独立。不同数据库向量的命中事件不必相互独立。
若只统计能够约化 \(x\) 的不同伙伴，则将第二式的求和范围限制到对应有效集合即可。不同伙伴数与实际接纳的新向量数仍需区分，见第 19 篇。
按直接计算 \(s\) 维内积的实现：
若编号去重和桶访问采用期望常数时间的字典操作，且每个不同候选都做一次真实长度检查，则
这里分别对应哈希计算、桶成员访问与候选检查。去重能减少重复内积计算，但已经读取的桶成员仍产生访问成本。
全部 \(t\) 张表同时驻留时，共保存 \(Nt\) 条成员引用。原向量坐标可以共享，不必复制 \(t\) 份完整向量；此外还需存储超平面、非空桶的键、管理信息和去重集合。使用非空桶字典，也避免为每张表预分配全部 \(2^k\) 个桶。
这些计数与成本是对上述固定流程的直接分析。提前停止、批量处理或改变索引布局后，应按实际操作重新计数。
6. 常见的参数指数 \(\rho\) 从哪里来#
先考虑单向查询，采用一个简化模型：
- 有一个希望找到的近点，与查询夹角至多为 \(\theta_1\)。
- 其余点都与查询相距至少 \(\theta_2\)。
- \(0<\theta_1<\theta_2<\pi\)，二者固定，不随 \(N\) 改变。
令
希望一张表中的远点候选数为常数量级，可以取
另一方面，近点的单表命中率至少为 \(p_1^k\)。为使固定近点的失败概率至多为常数 \(\delta\in(0,1)\)，取
即可，因为 \((1-p_1^k)^t\le e^{-tp_1^k}\)。
于是
在这个模型中，期望查询时间为 \(\widetilde O(sN^\rho)\)，表中的成员引用数为 \(O(N^{1+\rho})\)；\(\widetilde O\) 在此省略关于 \(N\) 的对数因子。预处理仍须付出建表成本。
这一近远分离模型与参数关系可对照 Becker–Ducas–Gama–Laarhoven，SODA 2016，§2 的 Lemma 2.3 及脚注 2，PDF 第 4 页。本节只分析上述简化输入与完整查桶流程。
取 \(\theta_1=\pi/3\)、\(\theta_2=\pi/2\)，得到
这个数描述特定近远阈值下的查询参数关系，不能直接当作筛法的时间指数。
实际筛法中，候选夹角分布在一个区间内。即使高维随机夹角集中在 \(90^\circ\) 附近，也不能把所有候选都替换为 \(90^\circ\)：若夹角为随机变量 \(\Theta\)，单向单表平均碰撞率是
通常不等于 \(p(\mathbb E[\Theta])^k\)。当数据库规模随维数指数增长时，非典型角度的贡献也可能影响总成本。
Laarhoven 在其 NV 型筛法的随机球面启发式、\(\gamma\to1\) 及优化参数下，得到时间估计 \(2^{0.3366s+o(s)}\)；这需要进一步分析角度分布与筛法流程。参见 原文 §4.2、Theorem 1 与 Appendix A。该结果不是任意输入上的最坏情况保证。
7. 接入筛法时需要保留哪些条件#
索引必须与向量状态一致。 数据库向量改变时，应移除旧键下的记录，再按新向量重新插入；若先将其移入待处理队列，则在重新接纳时建索引。查询向量改变后，也应重新计算键，旧候选集合不能视为对新方向的完整搜索结果。
HashSieve 的动态更新可对照 Laarhoven，§5.2、Algorithm 5，PDF 第 12 页。该节用角度约化说明理论动机，同时明确实际候选检查仍可采用真实范数条件。
固定索引上的重复查询没有增加独立机会。 当数据库、查询和表都不变时，再查一遍得到的仍是相同候选。多表覆盖公式来自独立采样的表，不能把相同查询的重复执行次数代入 \(t\)。
动态过程的概率分析需要另行核对。 本篇固定向量对的概率公式是精确计算；当后续向量由已有索引的查询结果产生时，它们可能与索引相关，不能未经论证就反复套用固定且独立的输入模型。
因此，没有命中约化伙伴只表示本次搜索未找到；它不能认证池已两两约化，也不能认证已找到最短向量。
后续可以继续阅读球面 LSF，再进入 BGJ 多层分桶。届时仍保留本篇的分析顺序：先确定共同命中概率，再计算重复访问与不同有效对覆盖，最后计入建桶、更新和内存成本。