角度 LSH 与多表搜索

前置笔记：高斯启发式与随机球面模型、Nguyen–Vidick、ListSieve 与 GaussSieve、筛法中的近邻搜索与分桶。

沿用近邻搜索与分桶的记号：当前维数为 $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 的随机超平面构造 [1, p. 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 放大的作用 [2, pp. 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{and}\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\|.

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

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$ 的不同伙伴，则将第二式的求和范围限制到对应有效集合即可。不同伙伴数与实际接纳的新向量数仍需区分，见近邻搜索与分桶。

按直接计算 $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$ 的对数因子。预处理仍须付出建表成本。

这一近远分离模型把候选生成的成本与近邻、远邻的碰撞概率联系起来 [3, p. 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)}$ [1, sec. 4.2]。这需要进一步分析角度分布与筛法流程。该结果不是任意输入上的最坏情况保证。

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

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

HashSieve 在数据库向量改变时同步更新相应的哈希表 [1, p. 12]。该算法用角度约化说明理论动机，同时明确实际候选检查仍可采用真实范数条件。

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

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

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

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

参考文献

1. Thijs Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. Advances in cryptology – CRYPTO 2015. 2015. DOI.

2. Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing. 2012. 原文.

3. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms. 2016. DOI.

角度 LSH 与多表搜索#

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

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

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

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

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

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

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

#参考文献