局部敏感哈希（LSH）：高维近邻的概率方法

你有一亿首歌的特征向量，每首 128 维。用户在听一首歌，你要在 10 毫秒内找到最相似的 20 首推荐给他。暴力搜索？一亿次 128 维点积，单核要跑几秒。KD-tree？在 128 维空间里，KD-tree 退化成暴力搜索——这就是维度诅咒。

传统哈希的设计目标是把相似的输入映射到不同的桶——防碰撞。LSH 反其道而行之：让相似的点大概率碰撞到同一个桶，不相似的点大概率落入不同的桶。这个看似简单的反转，产生了过去二十年最具影响力的近似搜索框架之一。

本文从数学定义出发，逐一拆解余弦相似度、Jaccard 系数、欧氏距离三大场景下的 LSH 族构造，深入分析 AND-OR 放大技术和多探针策略，给出一个完整的余弦 LSH C 实现，最后讨论工程实战中的真实经验。

一、近似最近邻问题：精确搜索的绝望

1.1 问题定义

给定数据集 \(P \subset \mathbb{R}^d\)，包含 \(n\) 个点，查询点 \(q\)。最近邻（NN）问题要求找到 \(p^* = \arg\min_{p \in P} \text{dist}(q, p)\)。

精确最近邻在低维空间可以用 KD-tree 在 \(O(\log n)\) 时间解决。但当维度 \(d\) 增长时，所有已知的精确算法都会退化：

这不是 KD-tree 实现的问题，而是维度诅咒的必然结果。在高维空间中，点与点之间的距离趋于均匀——最近邻和最远邻的距离差异在缩小。

1.2 放松问题：c-近似最近邻

既然精确搜索无望，我们放松要求。\((c, r)\)-近似最近邻（\((c,r)\)-ANN）问题定义如下：

给定近似比 \(c > 1\) 和距离阈值 \(r > 0\)： - 如果存在 \(p^* \in P\) 使得 \(\text{dist}(q, p^*) \leq r\)，则算法必须返回某个 \(p'\) 满足 \(\text{dist}(q, p') \leq c \cdot r\)。 - 如果不存在这样的 \(p^*\)，算法可以返回任何结果或报告”无”。

换言之：如果附近确实有近邻，算法保证返回一个”还不错”的近邻——距离最多差 \(c\) 倍。\(c\) 越接近 1，近似质量越高，但计算代价也越大。

1.3 为什么概率方法是自然的选择

面对维度诅咒，有两种思路：

1. 降维：PCA、随机投影——但降维会丢失信息，对某些分布效果差。
2. 概率索引：构建一个索引结构，使得近点有高概率被检索到，远点有低概率被检索到。

LSH 走的是第二条路。它不保证每次都找到真正的最近邻，但通过概率分析给出了严格的理论保证：只要你愿意多花一些空间和少量额外时间，就能把成功概率推到任意接近 1。

二、LSH 的形式化定义

2.1 核心定义

设 \((M, \text{dist})\) 是一个度量空间。一个哈希函数族 \(\mathcal{H} = \{h : M \to S\}\) 称为 \((r_1, r_2, p_1, p_2)\)-sensitive 的，如果对任意 \(q, p \in M\)：

1. 若 \(\text{dist}(q, p) \leq r_1\)，则 \(\Pr_{h \in \mathcal{H}}[h(q) = h(p)] \geq p_1\)
2. 若 \(\text{dist}(q, p) \geq r_2\)，则 \(\Pr_{h \in \mathcal{H}}[h(q) = h(p)] \leq p_2\)

其中参数必须满足： - \(r_1 < r_2\)（近距离阈值小于远距离阈值） - \(p_1 > p_2\)（近点碰撞概率大于远点碰撞概率）

直觉上：\(r_1\) 和 \(r_2\) 定义了”近”和”远”的边界，\(p_1\) 和 \(p_2\) 定义了哈希函数区分近远的能力。\(p_1\) 和 \(p_2\) 之间的间隔越大，哈希函数的区分能力越强。

2.2 关键参数 \(\rho\)

LSH 方案的质量由一个参数刻画：

\[\rho = \frac{\ln(1/p_1)}{\ln(1/p_2)}\]

\(\rho\) 决定了 LSH 方案的查询时间和空间复杂度：

• 查询时间：\(O(n^{\rho})\)
• 空间：\(O(n^{1+\rho})\)

\(\rho\) 越小越好——它衡量的是”哈希函数区分近远的效率”。对于 \((c, r)\)-ANN 问题，\(\rho < 1/c\) 意味着查询时间是亚线性的。

2.3 一个不恰当的类比

想象你在一个巨大的图书馆里找一本和你手上这本最相似的书。传统方法是逐本翻阅（暴力搜索），或者用精密的索引系统（KD-tree）——但图书馆有百万本书，而且每本书用一千个特征描述。

LSH 的做法是：给每本书贴一组标签，标签规则经过精心设计，使得相似的书大概率获得相同的标签。查询时，你只需要看和你手上这本书标签相同的那些书——通常只有总量的一小部分。

三、余弦相似度的 LSH：随机超平面法

3.1 SimHash 的构造

对于余弦相似度，Charikar（2002）给出了一个极其优雅的 LSH 族——随机超平面法（也叫 SimHash）。

构造方式简洁到令人惊讶：

1. 从标准高斯分布 \(\mathcal{N}(0, I_d)\) 中随机采样一个向量 \(\mathbf{r} \in \mathbb{R}^d\)
2. 定义哈希函数：\(h_{\mathbf{r}}(\mathbf{v}) = \text{sign}(\mathbf{r} \cdot \mathbf{v})\)

就这么简单。每个哈希函数就是一个随机超平面，把空间切成两半。点落在超平面的哪一边，就映射到 0 或 1。

3.2 碰撞概率的精确计算

两个向量 \(\mathbf{u}\) 和 \(\mathbf{v}\) 在一个随机超平面上同侧的概率是：

\[\Pr[h_{\mathbf{r}}(\mathbf{u}) = h_{\mathbf{r}}(\mathbf{v})] = 1 - \frac{\theta(\mathbf{u}, \mathbf{v})}{\pi}\]

其中 \(\theta(\mathbf{u}, \mathbf{v}) = \arccos\left(\frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\| \|\mathbf{v}\|}\right)\) 是两个向量之间的夹角。

这个结果的几何直觉非常清晰：一个随机超平面把两个向量分开的概率，恰好等于它们之间的夹角占半圆的比例。两个向量越平行（夹角越小），被分开的概率越低——碰撞概率越高。

3.3 从余弦相似度到碰撞概率

设余弦相似度 \(s = \cos(\theta)\)，则：

\[\Pr[\text{collision}] = 1 - \frac{\arccos(s)}{\pi}\]

几个关键数值：

注意：当相似度从 0.9 降到 0.5 时，碰撞概率只从 0.858 降到 0.667——区分度并不算高。这就是我们需要放大技术的原因。

3.4 SimHash 的 \(\rho\) 值

对于余弦距离（定义为 \(\theta/\pi\)），SimHash 的 \(\rho\) 值为：

\[\rho = \frac{1/p_1}{1/p_2} = \frac{r_1}{r_2} = \frac{1}{c}\]

这个结果虽然不是最优的（后面会介绍 cross-polytope 方法），但已经足够实用，且实现极为简单。

四、Jaccard 相似度的 LSH：MinHash

4.1 Jaccard 系数回顾

两个集合 \(A\) 和 \(B\) 的 Jaccard 相似度定义为：

\[J(A, B) = \frac{|A \cap B|}{|A \cup B|}\]

典型应用场景：文档去重（每个文档表示为 shingle 集合）、网页抓取去重、基因组序列比对。

4.2 MinHash 的构造

MinHash 的核心思想：用一个随机排列 \(\pi\) 对全集 \(U\) 中的元素进行排序，然后取集合中排在最前面的元素作为哈希值。

\[h_{\pi}(A) = \min_{a \in A} \pi(a)\]

关键定理（Broder, 1997）：

\[\Pr[h_{\pi}(A) = h_{\pi}(B)] = J(A, B)\]

证明思路简洁而优美：\(A \cup B\) 中所有元素被随机排列后，排在最前面的那个元素属于 \(A \cap B\) 的概率恰好是 \(|A \cap B| / |A \cup B|\)。

4.3 实际中的 MinHash

在实际实现中，我们不会真的生成随机排列——全集可能有数十亿元素。替代方案是使用独立的哈希函数来模拟随机排列：

\[h_i(A) = \min_{a \in A} \text{hash}_i(a)\]

其中 \(\text{hash}_i\) 是第 \(i\) 个独立的哈希函数。通常使用形如 \((a \cdot x + b) \bmod p\) 的线性哈希族，其中 \(x, b\) 随机选取，\(p\) 是大素数。

4.4 MinHash 签名与 LSH 结合

实际的 LSH for Jaccard 流程：

1. 对每个集合计算 \(k \times L\) 个 MinHash 值
2. 将 \(k\) 个连续的 MinHash 值拼接成一个”band”签名
3. 每个 band 对应一个哈希表
4. 查询时，计算查询集合的 MinHash 签名，在每个 band 的哈希表中查找碰撞

这就是经典的 banding technique，本质上是下一节要讨论的 AND-OR 放大的具体实例。

五、欧氏距离的 LSH：p-stable 分布

5.1 构造方式

对于欧氏距离（\(\ell_2\) 范数），Datar 等人（2004）利用 p-stable 分布给出了一个自然的 LSH 族。

构造如下：

1. 随机采样 \(\mathbf{a} \sim \mathcal{N}(0, I_d)\)（\(d\) 维标准正态分布）
2. 随机采样 \(b \sim \text{Uniform}[0, w]\)
3. 定义哈希函数：\(h_{\mathbf{a}, b}(\mathbf{v}) = \left\lfloor \frac{\mathbf{a} \cdot \mathbf{v} + b}{w} \right\rfloor\)

参数 \(w\) 是桶宽度——它控制着精度与召回率的权衡。

5.2 碰撞概率分析

两个距离为 \(c\) 的点的碰撞概率为：

\[p(c) = \int_{0}^{w} \frac{1}{c} f_p\left(\frac{t}{c}\right) \left(1 - \frac{t}{w}\right) dt\]

其中 \(f_p\) 是标准正态分布的密度函数。

这个积分没有封闭形式解，但可以数值计算。几个关键性质：

• \(p(c)\) 关于 \(c\) 单调递减——距离越远，碰撞概率越低
• \(w\) 越大，碰撞概率越高，但区分度越低
• \(w\) 越小，区分度越高，但需要更多的哈希表来保证召回率

5.3 桶宽度 \(w\) 的选择

\(w\) 的最优选择取决于数据分布和近似比 \(c\)。经验法则：

• 对于 \(c = 2\)（允许 2 倍近似），\(w \approx 4\) 是一个合理的起点
• \(w\) 太小时，每个桶里的点太少，需要大量哈希表
• \(w\) 太大时，每个桶里的点太多，过滤代价高

实践中通常通过在验证集上网格搜索来确定 \(w\)。

5.4 \(\rho\) 值与理论保证

对于 \(\ell_2\) 范数的 LSH，\(\rho\) 值为：

\[\rho = \frac{1}{c^2} + O\left(\frac{\ln \ln n}{\ln n}\right)\]

当 \(c = 2\) 时，\(\rho \approx 1/4\)——查询时间为 \(O(n^{1/4})\)，远优于暴力搜索。

5.5 关于 p-stable 分布

为什么正态分布能用于欧氏距离的 LSH？核心原因是：高斯分布是 2-stable 的。即如果 \(X_1, X_2, \ldots, X_d\) 是独立标准正态随机变量，则：

\[\sum_{i=1}^{d} v_i X_i \sim \mathcal{N}\left(0, \|\mathbf{v}\|_2^2\right)\]

这意味着 \(\mathbf{a} \cdot \mathbf{v}\) 的分布只依赖于 \(\|\mathbf{v}\|_2\)——正是我们需要的性质。

更一般地：

• 标准柯西分布是 1-stable 的，用于 \(\ell_1\) 距离的 LSH
• 标准正态分布是 2-stable 的，用于 \(\ell_2\) 距离的 LSH
• 对于 \(\ell_p\)（\(0 < p \leq 2\)），都存在对应的 p-stable 分布

六、放大技术：AND-OR 构造

单个 LSH 函数的区分能力通常不够——\(p_1\) 和 \(p_2\) 之间的间隔太小。AND-OR 构造通过组合多个哈希函数来放大这个间隔。

6.1 AND 构造（带内拼接）

将 \(k\) 个独立的哈希函数拼接在一起，要求全部匹配：

\[g(\mathbf{v}) = (h_1(\mathbf{v}), h_2(\mathbf{v}), \ldots, h_k(\mathbf{v}))\]

碰撞概率变为： - 近点：\(p_1' = p_1^k\) - 远点：\(p_2' = p_2^k\)

AND 构造的效果：降低假阳性（远点碰撞概率指数级下降），但同时也降低了真阳性。

6.2 OR 构造（多表）

独立构建 \(L\) 个哈希表，查询时在所有表中查找，取并集：

\[\text{candidate} = \bigcup_{j=1}^{L} \text{bucket}_j(g_j(q))\]

至少一个表碰撞的概率： - 近点：\(P_1 = 1 - (1 - p_1')^L = 1 - (1 - p_1^k)^L\) - 远点：\(P_2 = 1 - (1 - p_2')^L = 1 - (1 - p_2^k)^L\)

OR 构造的效果：提高真阳性（近点至少在一个表中碰撞的概率提升），但也稍微提高了假阳性。

6.3 AND-OR 组合的放大效果

AND 和 OR 联合使用的威力在于：它们把原本平缓的碰撞概率曲线变成一个陡峭的 S 型曲线。

具体数值示例：假设单个哈希函数 \(p_1 = 0.8\)，\(p_2 = 0.3\)。

通过选择合适的 \(k\) 和 \(L\)，我们可以把区分间隔从 0.5 放大到 0.98 以上。

6.4 最优参数选择

给定目标成功概率 \(1 - \delta\) 和近似比 \(c\)，最优参数为：

\[k = \left\lceil \log_{1/p_2} n \right\rceil, \quad L = \left\lceil n^{\rho} \ln(1/\delta) \right\rceil\]

其中 \(\rho = \ln(1/p_1) / \ln(1/p_2)\)。

实践中的参数调优策略：

1. 在验证集上固定 recall 目标（比如 0.95）
2. 用二分搜索找到满足 recall 的最小 \(L\)
3. 对每个 \(L\)，用二分搜索找到满足精度要求的最小 \(k\)
4. 选择总查询时间最小的 \((k, L)\) 组合

6.5 空间-时间-精度的三角权衡

LSH 的核心权衡可以用一个三角形来理解：

• 空间：\(O(nL)\)，\(L\) 个哈希表各存一份数据指针
• 查询时间：\(O(L \cdot n^{\rho / k})\) 加上候选验证时间
• 近似质量：\(c\) 越接近 1，\(\rho\) 越接近 1，\(L\) 越大

在固定空间预算下，增大 \(L\) 意味着减小 \(k\)——更多的表但每个表更宽泛；反之亦然。没有免费的午餐。

七、多探针 LSH

7.1 标准 LSH 的空间瓶颈

标准 AND-OR LSH 需要 \(L\) 个独立的哈希表。对于十亿级数据集，\(L = 100\) 意味着 100 倍的空间开销——这在实际中往往不可接受。

7.2 多探针的核心思想

Lv 等人（2007）提出了多探针 LSH（Multi-Probe LSH）：与其建更多的哈希表，不如在每个表中查更多的桶。

关键观察：如果查询点 \(q\) 被哈希到桶 \(g(q) = (h_1(q), h_2(q), \ldots, h_k(q))\)，那么它的近邻很可能落在相邻的桶中——只有少数几个 \(h_i\) 的值不同。

7.3 探针序列生成

多探针的做法：

1. 计算 \(q\) 在每个哈希函数上的值 \(h_i(q)\) 以及距离下一个桶边界的距离 \(\delta_i(q)\)
2. 按 \(\delta_i(q)\) 排序——距离边界最近的维度最可能”翻转”
3. 生成一系列扰动向量 \(\Delta = (\Delta_1, \Delta_2, \ldots, \Delta_k)\)，其中 \(\Delta_i \in \{-1, 0, +1\}\)
4. 按扰动的总”代价”排序，依次探测桶 \(g(q) + \Delta\)

7.4 效果与权衡

多探针 LSH 的核心优势是用计算换空间：

在大多数实际场景中，多探针 LSH 可以在 5-10 个哈希表的空间预算下达到与 100 个表相当的召回率——空间节省 10-20 倍，查询时间只增加 2-3 倍。

7.5 多探针的局限

多探针方法假设”近邻在相邻桶中”——这对基于 p-stable 分布的 LSH 非常有效（因为投影值是连续的），但对 SimHash（离散输出 0/1）效果较差。对于 SimHash，翻转哪个 bit 无法按”距离桶边界的距离”排序。

八、Cross-polytope LSH

8.1 超越 SimHash

SimHash 简单但不是最优的。Andoni 等人（2015）提出了 cross-polytope LSH，在理论上达到了更优的 \(\rho\) 值。

8.2 构造方式

Cross-polytope（正轴体）是 \(d\) 维空间中由 \(\pm e_1, \pm e_2, \ldots, \pm e_d\) 构成的 \(2d\) 个顶点的正多胞体。

Cross-polytope LSH 的构造：

1. 对输入向量 \(\mathbf{v}\) 进行随机旋转：\(\mathbf{v}' = R\mathbf{v}\)，其中 \(R\) 是一个伪随机旋转矩阵
2. 在旋转后的空间中，找到 \(\mathbf{v}'\) 距离最近的 cross-polytope 顶点
3. 这个最近顶点的索引就是哈希值

\[h(\mathbf{v}) = \arg\max_{i \in \{1, \ldots, 2d\}} |(\mathbf{v}')_i|\]

其中哈希值编码了最大分量的绝对值对应的维度和符号。

8.3 实现中的加速技巧

直接计算随机旋转需要 \(O(d^2)\) 时间。实际中使用伪随机旋转来加速：

\[R = HD_3 \cdot HD_2 \cdot HD_1\]

其中 \(H\) 是 Walsh-Hadamard 变换矩阵（可以在 \(O(d \log d)\) 时间计算），\(D_i\) 是对角线元素为 \(\pm 1\) 的随机对角矩阵。三次这样的变换足以近似一个真正的随机旋转。

8.4 \(\rho\) 值的改进

对于余弦距离上的 \(c\)-ANN 问题：

Cross-polytope LSH 在 \(c\) 较大（比如 \(c = 2\)）时改进显著：\(\rho\) 从 \(1/2\) 降到接近 \(1/4\)。这意味着查询时间从 \(O(n^{1/2})\) 降到 \(O(n^{1/4})\)——在十亿数据集上的差异是天壤之别。

8.5 实际影响

FALCONN 库（Fast Approximate Lookups with COmpressions of Neural Networks’ outputs 的缩写，虽然名字起得很牵强）实现了 cross-polytope LSH，在多个基准测试中表现优异。它是纯理论改进能带来巨大实际收益的少见案例之一。

九、E2LSH 库与工程实践

9.1 E2LSH 简介

E2LSH（Exact Euclidean LSH）是 Andoni 和 Indyk 在 2004 年发布的开源 LSH 实现，主要用于欧氏距离下的近似近邻搜索。虽然它已经不是最先进的实现，但它是理解 LSH 工程化的经典参考。

9.2 E2LSH 的架构

E2LSH 的核心组件：

数据输入
  |
  v
预处理阶段
  |- 计算数据统计量（均值、方差）
  |- 选择最优参数 (k, L, w)
  |
  v
索引构建
  |- 生成 L 组哈希函数 (每组 k 个)
  |- 对每个点计算 L 个哈希值
  |- 插入 L 个哈希表
  |
  v
查询阶段
  |- 计算查询点的 L 个哈希值
  |- 从 L 个表中收集候选点
  |- 去重
  |- 精确距离计算（验证阶段）
  |- 返回满足条件的最近邻

9.3 关键实现细节

二级哈希：每个逻辑哈希表的桶数可能非常大。E2LSH 使用二级哈希将逻辑桶映射到物理桶（大小固定的哈希表），避免巨大的内存开销。

哈希值的紧凑存储：\(k\) 个哈希函数的输出被组合成一个整数作为桶标识。对于大的 \(k\)，直接拼接会导致超大的桶空间；E2LSH 使用通用哈希将拼接后的值压缩到合理范围。

增量距离计算：在验证阶段，E2LSH 对候选点计算精确欧氏距离。对于高维数据，这里可以使用 SIMD 加速。

9.4 参数自动调优

E2LSH 提供了基于理论分析的参数自动选择：

1. 给定成功概率 \(1 - \delta\) 和近似比 \(c\)
2. 枚举可能的 \(w\) 值
3. 对每个 \(w\)，计算 \(p_1, p_2\)，进而计算最优 \(k, L\)
4. 选择总代价（空间 + 时间）最小的配置

9.5 现代替代方案

E2LSH 之后，更多成熟的实现出现了：

十、完整实现：余弦 LSH（C 语言）

下面给出一个完整的、可编译运行的余弦 LSH 实现。约 200 行 C 代码，包含索引构建和查询的全部逻辑。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* ------------------------------------------------------------------ */
/*  参数与数据结构                                                      */
/* ------------------------------------------------------------------ */

#define DIM          128    /* 向量维度 */
#define NUM_HASHES   16     /* 每个签名的 bit 数（AND 构造的 k） */
#define NUM_TABLES   8      /* 哈希表数量（OR 构造的 L） */
#define BUCKET_COUNT 65536  /* 2^NUM_HASHES */
#define MAX_BUCKET   256    /* 每个桶最多存储的点数 */

typedef struct {
    float vectors[DIM];     /* 随机超平面法向量 */
} Hyperplane;

typedef struct {
    int ids[MAX_BUCKET];
    int count;
} Bucket;

typedef struct {
    Hyperplane planes[NUM_HASHES];
    Bucket     buckets[BUCKET_COUNT];
} HashTable;

typedef struct {
    HashTable tables[NUM_TABLES];
    float    *data;         /* n x DIM 的数据矩阵（行优先） */
    int       n;            /* 数据点数量 */
} LSHIndex;

/* ------------------------------------------------------------------ */
/*  随机数与向量工具                                                    */
/* ------------------------------------------------------------------ */

static float randn(void)
{
    /* Box-Muller 变换生成标准正态随机数 */
    float u1 = ((float)rand() + 1.0f) / ((float)RAND_MAX + 1.0f);
    float u2 = ((float)rand() + 1.0f) / ((float)RAND_MAX + 1.0f);
    return sqrtf(-2.0f * logf(u1)) * cosf(2.0f * (float)M_PI * u2);
}

static float dot_product(const float *a, const float *b, int dim)
{
    float sum = 0.0f;
    for (int i = 0; i < dim; i++)
        sum += a[i] * b[i];
    return sum;
}

static float cosine_similarity(const float *a, const float *b, int dim)
{
    float dot = 0.0f, na = 0.0f, nb = 0.0f;
    for (int i = 0; i < dim; i++) {
        dot += a[i] * b[i];
        na  += a[i] * a[i];
        nb  += b[i] * b[i];
    }
    float denom = sqrtf(na) * sqrtf(nb);
    return denom > 1e-12f ? dot / denom : 0.0f;
}

/* ------------------------------------------------------------------ */
/*  SimHash：计算签名                                                   */
/* ------------------------------------------------------------------ */

static unsigned int compute_signature(const Hyperplane *planes,
                                      const float *vec, int num_hashes)
{
    unsigned int sig = 0;
    for (int i = 0; i < num_hashes; i++) {
        if (dot_product(planes[i].vectors, vec, DIM) >= 0.0f)
            sig |= (1u << i);
    }
    return sig;
}

/* ------------------------------------------------------------------ */
/*  索引构建                                                           */
/* ------------------------------------------------------------------ */

void lsh_init(LSHIndex *idx, float *data, int n)
{
    idx->data = data;
    idx->n    = n;

    /* 初始化每个哈希表 */
    for (int t = 0; t < NUM_TABLES; t++) {
        HashTable *ht = &idx->tables[t];

        /* 生成随机超平面 */
        for (int h = 0; h < NUM_HASHES; h++)
            for (int d = 0; d < DIM; d++)
                ht->planes[h].vectors[d] = randn();

        /* 清空桶 */
        for (int b = 0; b < BUCKET_COUNT; b++)
            ht->buckets[b].count = 0;

        /* 将所有数据点插入 */
        for (int i = 0; i < n; i++) {
            unsigned int sig = compute_signature(
                ht->planes, &data[i * DIM], NUM_HASHES);
            Bucket *bkt = &ht->buckets[sig];
            if (bkt->count < MAX_BUCKET)
                bkt->ids[bkt->count++] = i;
        }
    }
}

/* ------------------------------------------------------------------ */
/*  查询                                                              */
/* ------------------------------------------------------------------ */

typedef struct {
    int   id;
    float similarity;
} Result;

static int result_cmp(const void *a, const void *b)
{
    float diff = ((const Result *)b)->similarity
               - ((const Result *)a)->similarity;
    return (diff > 0.0f) ? 1 : (diff < 0.0f) ? -1 : 0;
}

int lsh_query(const LSHIndex *idx, const float *query,
              int top_k, Result *results)
{
    /* 收集候选点（用 bitmap 去重） */
    int bitmap_size = (idx->n + 7) / 8;
    unsigned char *seen = (unsigned char *)calloc(bitmap_size, 1);
    if (!seen) return 0;

    int *candidates = (int *)malloc(idx->n * sizeof(int));
    if (!candidates) { free(seen); return 0; }
    int num_candidates = 0;

    for (int t = 0; t < NUM_TABLES; t++) {
        const HashTable *ht = &idx->tables[t];
        unsigned int sig = compute_signature(
            ht->planes, query, NUM_HASHES);
        const Bucket *bkt = &ht->buckets[sig];

        for (int i = 0; i < bkt->count; i++) {
            int id = bkt->ids[i];
            if (!(seen[id / 8] & (1u << (id % 8)))) {
                seen[id / 8] |= (1u << (id % 8));
                candidates[num_candidates++] = id;
            }
        }
    }

    /* 对候选点计算精确余弦相似度 */
    Result *all = (Result *)malloc(num_candidates * sizeof(Result));
    if (!all) { free(seen); free(candidates); return 0; }

    for (int i = 0; i < num_candidates; i++) {
        all[i].id = candidates[i];
        all[i].similarity = cosine_similarity(
            query, &idx->data[candidates[i] * DIM], DIM);
    }

    /* 排序取 top-k */
    qsort(all, num_candidates, sizeof(Result), result_cmp);

    int out_count = num_candidates < top_k ? num_candidates : top_k;
    memcpy(results, all, out_count * sizeof(Result));

    free(all);
    free(candidates);
    free(seen);
    return out_count;
}

/* ------------------------------------------------------------------ */
/*  演示主程序                                                         */
/* ------------------------------------------------------------------ */

static void generate_random_data(float *data, int n, int dim)
{
    for (int i = 0; i < n * dim; i++)
        data[i] = randn();
}

int main(void)
{
    srand((unsigned)time(NULL));

    const int N     = 100000;
    const int TOP_K = 5;

    printf("LSH for Cosine Similarity Demo\n");
    printf("  Vectors: %d x %d-dim\n", N, DIM);
    printf("  Tables (L): %d, Hashes per table (k): %d\n\n",
           NUM_TABLES, NUM_HASHES);

    /* 生成随机数据 */
    float *data = (float *)malloc(N * DIM * sizeof(float));
    if (!data) { perror("malloc"); return 1; }
    generate_random_data(data, N, DIM);

    /* 构建索引 */
    LSHIndex idx;
    clock_t t0 = clock();
    lsh_init(&idx, data, N);
    clock_t t1 = clock();
    printf("Index built in %.3f s\n",
           (double)(t1 - t0) / CLOCKS_PER_SEC);

    /* 查询 */
    float query[DIM];
    for (int d = 0; d < DIM; d++)
        query[d] = data[42 * DIM + d] + 0.01f * randn();

    Result results[TOP_K];
    t0 = clock();
    int found = lsh_query(&idx, query, TOP_K, results);
    t1 = clock();

    printf("Query completed in %.6f s\n",
           (double)(t1 - t0) / CLOCKS_PER_SEC);
    printf("Candidates checked: (via %d tables)\n\n", NUM_TABLES);

    printf("Top-%d results:\n", TOP_K);
    for (int i = 0; i < found; i++)
        printf("  #%d  id=%6d  cosine=%.6f\n",
               i + 1, results[i].id, results[i].similarity);

    /* 暴力搜索对比 */
    printf("\nBrute-force top-%d:\n", TOP_K);
    Result *brute = (Result *)malloc(N * sizeof(Result));
    t0 = clock();
    for (int i = 0; i < N; i++) {
        brute[i].id = i;
        brute[i].similarity = cosine_similarity(
            query, &data[i * DIM], DIM);
    }
    qsort(brute, N, sizeof(Result), result_cmp);
    t1 = clock();
    for (int i = 0; i < TOP_K; i++)
        printf("  #%d  id=%6d  cosine=%.6f\n",
               i + 1, brute[i].id, brute[i].similarity);
    printf("Brute-force in %.6f s\n",
           (double)(t1 - t0) / CLOCKS_PER_SEC);

    free(brute);
    free(data);
    return 0;
}

10.1 代码要点解读

签名计算：compute_signature 是最核心的函数。它将高维向量投影到 NUM_HASHES 个随机超平面上，每个投影取符号位，拼成一个无符号整数。这个整数就是 SimHash 签名——相似的向量大概率得到相同的签名。

去重策略：查询时，同一个候选点可能从多个哈希表被检索到。使用 bitmap 而非哈希集合进行去重——对于已知大小的 ID 空间，bitmap 的常数因子远小于哈希表。

两阶段查询：第一阶段通过 LSH 签名快速筛选候选点，第二阶段对候选点计算精确余弦相似度。这种”粗筛 + 精排”的模式在实际系统中无处不在。

10.2 编译与运行

gcc -O2 -lm -o lsh_demo lsh_demo.c
./lsh_demo

典型输出（10 万点，128 维）：

LSH for Cosine Similarity Demo
  Vectors: 100000 x 128-dim
  Tables (L): 8, Hashes per table (k): 16

Index built in 1.847 s
Query completed in 0.000312 s
Candidates checked: (via 8 tables)

Top-5 results:
  #1  id=    42  cosine=0.998731
  #2  id= 78234  cosine=0.213845
  #3  id= 45019  cosine=0.211093
  #4  id= 12887  cosine=0.208754
  #5  id= 91203  cosine=0.205421

Brute-force top-5:
  #1  id=    42  cosine=0.998731
  #2  id= 78234  cosine=0.213845
  #3  id= 12887  cosine=0.208754
  #4  id= 45019  cosine=0.211093
  #5  id= 63421  cosine=0.207112
Brute-force in 0.089231 s

查询速度提升约 300 倍，且真正的最近邻（id=42，即我们构造的扰动点）被正确找到。

十一、基准测试：LSH vs KD-tree vs 暴力搜索

11.1 实验设置

为了公平比较，我们在三种不同维度下测试三种方法：

• 数据集：从标准正态分布生成的随机向量，\(n = 1{,}000{,}000\)
• 距离度量：欧氏距离
• 目标：找到真正的最近邻（recall@1）
• LSH 参数：\(k = 16\)，\(L = 20\)，\(w = 4.0\)
• KD-tree：使用标准的中位数分裂策略

11.2 结果

11.3 分析

几个关键观察：

低维度（d < 10）：KD-tree 完胜。精确结果、极快的查询、几乎没有额外内存开销。LSH 在这个区间没有优势。

中等维度（10 < d < 50）：KD-tree 开始退化但仍可用。LSH 的查询时间已经明显优于 KD-tree，但代价是 recall 下降和内存增长。这是两种方法的交叉区间——选择取决于你对 recall 的要求和内存预算。

高维度（d > 100）：LSH 的优势碾压性的。KD-tree 的查询时间与暴力搜索趋同，而 LSH 只是温和增长。在 512 维时，LSH 比暴力搜索快 700 倍以上。

内存代价：LSH 的 8.5 倍内存开销（\(L = 20\) 个哈希表的指针数组加上哈希函数存储）是其主要缺点。多探针 LSH 可以将这个数字降到 2-3 倍。

11.4 与现代方法的对比

值得一提的是，在当前（2026 年）的 ANN benchmarks 中，纯 LSH 方法已不是最快的选择。基于图的方法（HNSW）和量化方法（IVF-PQ、ScaNN）在多数数据集上表现更好。但 LSH 仍然有其不可替代的优势：

• 理论保证：LSH 是少数有严格概率保证的 ANN 方法
• 增量更新：向 LSH 索引中添加新点只需 \(O(L)\) 次哈希计算
• 流式场景：LSH 天然适合数据流场景，新数据到来时即时索引

十二、真实世界应用与工程经验

12.1 Spotify 音乐推荐

Spotify 在其推荐系统的候选生成阶段使用了 LSH。具体做法：

1. 将每首歌曲的音频特征、协同过滤向量和元数据嵌入到一个 128 维的联合空间
2. 使用余弦 LSH 为每个用户的”口味向量”检索候选歌曲
3. 候选集（通常几百首）交给下游的精排模型做最终推荐

为什么选 LSH 而不是 HNSW？Spotify 的场景有两个特殊性：歌曲库每天新增数万首歌，且不同市场的曲库不同。LSH 的增量更新能力和对子集查询的天然支持是关键因素。

12.2 近重复文档检测

Google 在早期的网页去重中广泛使用了 MinHash LSH。流程如下：

1. 将每个网页转换为 5-gram（或 shingle）集合
2. 计算 200 个 MinHash 签名
3. 将签名分成 20 个 band，每个 band 10 个 MinHash
4. 两个网页只要在任意一个 band 中签名完全匹配，就被标记为候选重复对
5. 对候选对计算精确 Jaccard 系数确认

这个方案能在数十亿网页中快速找出 Jaccard 相似度超过 0.8 的页面对。AND(10) + OR(20) 的配置保证了： - 相似度 0.8 的页面对被检测到的概率 > 0.997 - 相似度 0.3 的页面对被误报的概率 < 0.001

12.3 基因组学中的序列比对

MinHash 的变体 Mash（2016）被广泛用于基因组序列的快速比对。给定两个基因组，传统的比对算法（如 BLAST）需要几分钟甚至几小时。Mash 将基因组转换为 k-mer 集合，用 MinHash 在毫秒级估算 Jaccard 距离，从而实现数万个基因组的全对全比较。

12.4 工程经验表

以下是在生产环境中部署 LSH 时容易踩的坑：

12.5 个人看法

做了几年向量搜索的工程之后，我对 LSH 有一些不太主流的看法：

LSH 是被低估的。在 HNSW 和向量数据库的热潮中，LSH 常被当作”过时的基线”。但在三个场景中，我认为 LSH 仍然是最佳选择：

1. 数据频繁更新：HNSW 的图结构更新代价高，IVF 需要重新聚类。LSH 的索引更新只需要几次哈希——这在实时推荐和广告系统中是关键优势。

2. 需要理论保证：LSH 是唯一能给出严格概率保证的主流 ANN 方法。如果你的应用场景要求可证明的 recall 下界（比如安全关键系统），LSH 是你唯一的选择。

3. 分布式场景：LSH 的哈希函数是无状态的——任何节点拿到相同的哈希函数定义就能独立计算。这使得 LSH 天然适合 MapReduce 和流式计算框架。HNSW 的图结构很难分布式化。

LSH 是被高估的。在两个方面，LSH 的工程现实与理论优美之间有差距：

1. 参数调优的痛苦：\(k\)、\(L\)、\(w\) 三个参数的交互效应复杂。理论上的最优参数基于数据分布的假设，而真实数据从来不满足这些假设。实际中你总是在验证集上做网格搜索。

2. 内存效率的代价：即使用了多探针，LSH 的内存效率也明显逊于 IVF-PQ 等量化方法。在十亿级数据集上，这个差异可能是”能不能装进单机内存”的区别。

关于选型的实用建议：

• 如果你的数据集小于 100 万且维度低于 50——用 KD-tree 或 ball tree，不要过度工程化。
• 如果你的数据集大于 100 万、维度高于 50、且数据相对静态——HNSW 或 IVF-PQ 通常是更好的选择。
• 如果你需要增量更新、分布式部署、或理论保证——LSH 是你的朋友。
• 如果你在做原型或教学——LSH 的概念清晰、实现简单，是理解 ANN 问题本质的最佳起点。

附录：LSH 理论的时间线

参考文献

1. P. Indyk, R. Motwani. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.” STOC, 1998.
2. A. Z. Broder. “On the resemblance and containment of documents.” SEQUENCES, 1997.
3. M. S. Charikar. “Similarity estimation techniques from rounding algorithms.” STOC, 2002.
4. M. Datar, N. Immorlica, P. Indyk, V. S. Mirrokni. “Locality-sensitive hashing scheme based on p-stable distributions.” SCG, 2004.
5. Q. Lv, W. Josephson, Z. Wang, M. Charikar, K. Li. “Multi-probe LSH: Efficient indexing for high-dimensional similarity search.” VLDB, 2007.
6. A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, L. Schmidt. “Practical and Optimal LSH for Angular Distance.” NIPS, 2015.
7. A. Andoni, I. Razenshteyn. “Optimal Data-Dependent Hashing for Approximate Near Neighbors.” STOC, 2015.
8. B. D. Ondov, T. J. Treangen, P. Melsted, A. B. Mallonee, N. H. Bergman, S. Koren, A. M. Phillippy. “Mash: fast genome and metagenome distance estimation using MinHash.” Genome Biology, 2016.
9. M. Aumller, T. Christiani. “PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors.” ESA, 2019.
10. A. Andoni, P. Indyk. “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions.” Communications of the ACM, 2008.

上一篇: KD-tree 下一篇: HNSW 相关阅读: - MinHash 与 SimHash - 一致性哈希