20 角度 LSH 与多表搜索

整理日期：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$ ，记其夹角为

\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 页核对。

因此，夹角越小，同键概率越大。例如， $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 页。

两个参数的作用不同：

增大 $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$ ，也不提前停止。

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 页。本节只分析上述简化输入与完整查桶流程。

取 $\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。该结果不是任意输入上的最坏情况保证。

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

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

HashSieve 的动态更新可对照 Laarhoven，§5.2、Algorithm 5，PDF 第 12 页。该节用角度约化说明理论动机，同时明确实际候选检查仍可采用真实范数条件。

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

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

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

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

20 角度 LSH 与多表搜索#

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

#2. 多位组合与多表放大

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

#4. 固定数据库上的候选查询

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

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

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

#引用此笔记