# 20 角度 LSH 与多表搜索

整理日期：2026-10-16。  
适用范围：随机超平面角度 LSH 的候选生成、多表覆盖、参数选择，以及与两向量筛法的衔接。  
前置笔记：[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)、[18 Nguyen–Vidick、ListSieve 与 GaussSieve](/knowledge/nguyen-vidick-listsieve-and-gausssieve/)、[19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)。

沿用第 19 篇的记号：当前维数为 $s\ge2$，非零向量池为 $D=\{x_1,\ldots,x_N\}$。本篇先研究固定数据库 $D$ 与固定非零查询向量 $x\notin D$，并假设它们与随机哈希函数的选择独立。

核心思路是：用多个随机超平面的符号组成桶键，再用多张独立的表提高近邻命中率。桶只负责产生候选，是否能够约化仍由真实长度决定。

## 1. 随机超平面为什么对角度敏感

对非零向量 $x,y$，记其夹角为

$$
\theta(x,y)=\arccos\frac{\langle x,y\rangle}{\|x\|\|y\|}\in[0,\pi].
$$

从单位球面均匀采样法向量 $a$，定义一位哈希

$$
h_a(x)=\mathbf 1\{\langle a,x\rangle\ge0\}.
$$

超平面 $a^\perp$ 把空间分成两侧，同侧向量取得相同的位。

在包含 $x,y$ 的二维平面内，随机分界线将两者分开的概率为 $\theta/\pi$，所以

$$
\boxed{
p(\theta)=\Pr[h_a(x)=h_a(y)]
=1-\frac{\theta}{\pi}.
}
$$

这是 Charikar 的随机超平面构造。本篇按 [Laarhoven，CRYPTO 2015，ePrint 2014/744 的 23 页版，§2.5，式 (2)–(4)，PDF 第 6 页](https://eprint.iacr.org/2014/744.pdf) 核对。

因此，夹角越小，同键概率越大。例如，$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$ 的向量对，其单表碰撞概率为

$$
q_k(\theta)=p(\theta)^k.
$$

**多表搜索只要求至少一张表命中。** 查询每张表的同键桶后，覆盖概率为

$$
\boxed{
P_{k,t}(\theta)
=1-\left(1-p(\theta)^k\right)^t.
}
$$

这分别是 AND 组合与 OR 放大的作用。多表索引的基本构造也可参见 [Har-Peled–Indyk–Motwani，Theory of Computing 2012，§3.2，PDF 第 17–18 页](https://www.theoryofcomputing.org/articles/v008a014/v008a014.pdf)。

两个参数的作用不同：

- 增大 $k$：近点和远点都更难碰撞，但远点的概率下降得更快，候选更少。
- 增大 $t$：提高覆盖率，同时增加建表、查询和索引存储成本。

若某个固定目标的单表命中率为 $q\in(0,1)$，希望漏检概率不超过 $\delta$，则

$$
t\ge
\frac{\ln\delta}{\ln(1-q)}
\approx\frac{\ln(1/\delta)}{q},
\qquad q\ll1.
$$

这是对一个固定目标的要求。它既不表示命中次数等于不同候选数，也不直接保证全部有效对都被覆盖。

## 3. 筛法为什么要查询正负两个方向

两向量约化需要同时考虑 $x-y$ 与 $x+y$。若只查 $g_\ell(x)$，就偏向寻找与 $x$ 同向的伙伴，容易遗漏接近 $-x$ 的伙伴。

一种直接设计是：每条数据库向量在每张表中只存一次；查询时读取

$$
T_\ell[g_\ell(x)]
\quad\text{和}\quad
T_\ell[g_\ell(-x)].
$$

在连续随机模型中，固定非零向量落在超平面上的概率为零，因而几乎必然有

$$
g_\ell(-x)=\overline{g_\ell(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$，也不提前停止。

~~~text
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$，可以令

$$
w=x-\sigma y,
\qquad
\sigma=
\begin{cases}
1,&\langle x,y\rangle\ge0,\\
-1,&\langle x,y\rangle<0,
\end{cases}
$$

并检查

$$
0<\|w\|<\|x\|.
$$

这与第 19 篇中“缩短两者的较长者”采用的判据不同。若外层算法使用目标半径、双向约化或其他接纳规则，应保留对应条件。

## 5. 重复访问、不同候选与实际成本

记 $\theta_j=\theta(x,x_j)$，并令

$$
q_j=q_k^\pm(\theta_j).
$$

对第 4 节的完整查询，定义：

- $C_{\mathrm{raw}}$：从各表读取的桶成员总数，包含跨表重复。
- $C_{\mathrm{unique}}$：去重后的不同候选编号数。

对随机索引取期望，有

$$
\boxed{
\mathbb E[C_{\mathrm{raw}}]
=t\sum_{j=1}^{N}q_j,
\qquad
\mathbb E[C_{\mathrm{unique}}]
=\sum_{j=1}^{N}\left[1-(1-q_j)^t\right].
}
$$

第一式只用期望的线性性；第二式还使用同一向量对在不同表中的命中事件独立。不同数据库向量的命中事件不必相互独立。

若只统计能够约化 $x$ 的不同伙伴，则将第二式的求和范围限制到对应有效集合即可。不同伙伴数与实际接纳的新向量数仍需区分，见第 19 篇。

按直接计算 $s$ 维内积的实现：

$$
T_{\mathrm{build}}=O(sNkt).
$$

若编号去重和桶访问采用期望常数时间的字典操作，且每个不同候选都做一次真实长度检查，则

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

这里分别对应哈希计算、桶成员访问与候选检查。去重能减少重复内积计算，但已经读取的桶成员仍产生访问成本。

全部 $t$ 张表同时驻留时，共保存 $Nt$ 条成员引用。原向量坐标可以共享，不必复制 $t$ 份完整向量；此外还需存储超平面、非空桶的键、管理信息和去重集合。使用非空桶字典，也避免为每张表预分配全部 $2^k$ 个桶。

这些计数与成本是对上述固定流程的直接分析。提前停止、批量处理或改变索引布局后，应按实际操作重新计数。

## 6. 常见的参数指数 $\rho$ 从哪里来

先考虑**单向查询**，采用一个简化模型：

- 有一个希望找到的近点，与查询夹角至多为 $\theta_1$。
- 其余点都与查询相距至少 $\theta_2$。
- $0<\theta_1<\theta_2<\pi$，二者固定，不随 $N$ 改变。

令

$$
p_1=1-\frac{\theta_1}{\pi},
\qquad
p_2=1-\frac{\theta_2}{\pi},
\qquad
p_1>p_2.
$$

希望一张表中的远点候选数为常数量级，可以取

$$
k=
\left\lceil
\frac{\ln N}{\ln(1/p_2)}
\right\rceil,
\qquad
Np_2^k\le1.
$$

另一方面，近点的单表命中率至少为 $p_1^k$。为使固定近点的失败概率至多为常数 $\delta\in(0,1)$，取

$$
t=
\left\lceil
\frac{\ln(1/\delta)}{p_1^k}
\right\rceil
$$

即可，因为 $(1-p_1^k)^t\le e^{-tp_1^k}$。

于是

$$
\boxed{
\rho=
\frac{\ln(1/p_1)}{\ln(1/p_2)},
\qquad
t=\Theta(N^\rho).
}
$$

在这个模型中，期望查询时间为 $\widetilde O(sN^\rho)$，表中的成员引用数为 $O(N^{1+\rho})$；$\widetilde O$ 在此省略关于 $N$ 的对数因子。预处理仍须付出建表成本。

这一近远分离模型与参数关系可对照 [Becker–Ducas–Gama–Laarhoven，SODA 2016，§2 的 Lemma 2.3 及脚注 2，PDF 第 4 页](https://ir.cwi.nl/pub/23692/23692.pdf)。本节只分析上述简化输入与完整查桶流程。

取 $\theta_1=\pi/3$、$\theta_2=\pi/2$，得到

$$
\rho=
\frac{\ln(3/2)}{\ln2}
=\log_2(3/2)
\approx0.585.
$$

这个数描述特定近远阈值下的查询参数关系，不能直接当作筛法的时间指数。

实际筛法中，候选夹角分布在一个区间内。即使高维随机夹角集中在 $90^\circ$ 附近，也不能把所有候选都替换为 $90^\circ$：若夹角为随机变量 $\Theta$，单向单表平均碰撞率是

$$
\mathbb E[p(\Theta)^k],
$$

通常不等于 $p(\mathbb E[\Theta])^k$。当数据库规模随维数指数增长时，非典型角度的贡献也可能影响总成本。

Laarhoven 在其 NV 型筛法的随机球面启发式、$\gamma\to1$ 及优化参数下，得到时间估计 $2^{0.3366s+o(s)}$；这需要进一步分析角度分布与筛法流程。参见 [原文 §4.2、Theorem 1 与 Appendix A](https://eprint.iacr.org/2014/744.pdf)。该结果不是任意输入上的最坏情况保证。

## 7. 接入筛法时需要保留哪些条件

**索引必须与向量状态一致。** 数据库向量改变时，应移除旧键下的记录，再按新向量重新插入；若先将其移入待处理队列，则在重新接纳时建索引。查询向量改变后，也应重新计算键，旧候选集合不能视为对新方向的完整搜索结果。

HashSieve 的动态更新可对照 [Laarhoven，§5.2、Algorithm 5，PDF 第 12 页](https://eprint.iacr.org/2014/744.pdf)。该节用角度约化说明理论动机，同时明确实际候选检查仍可采用真实范数条件。

**固定索引上的重复查询没有增加独立机会。** 当数据库、查询和表都不变时，再查一遍得到的仍是相同候选。多表覆盖公式来自独立采样的表，不能把相同查询的重复执行次数代入 $t$。

**动态过程的概率分析需要另行核对。** 本篇固定向量对的概率公式是精确计算；当后续向量由已有索引的查询结果产生时，它们可能与索引相关，不能未经论证就反复套用固定且独立的输入模型。

因此，没有命中约化伙伴只表示本次搜索未找到；它不能认证池已两两约化，也不能认证已找到最短向量。

后续可以继续阅读球面 LSF，再进入 BGJ 多层分桶。届时仍保留本篇的分析顺序：先确定共同命中概率，再计算重复访问与不同有效对覆盖，最后计入建桶、更新和内存成本。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)
- [22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)