HNSW 的基础实现和优化探索

感谢 wibyuan 对优化探索过程中的讨论和建议。

问题引入

向量检索是指从一个实数向量集合 \(\mathcal{B}=\{v_1,v_2,..., v_n \} \subseteq R^{n\times d}\) 中，找到与查询向量 \(q \in R^d\) 最相似的向量集合 \(\mathcal{R}=\{v_{i_1}, v_{i_2}, ..., v_{i_k}\}\) 的过程

最相似的 K 个向量被称为 K 近邻（K Nearest Neighbors, KNN）

在大模型时代，向量检索被广泛应用于文本检索、图像检索、推荐系统等领域

这里的相似常用的有三种：

\(L2\) 相似度：\(sim(q, v) = -||q-v||_2\)
内积相似度：\(sim(q, v) = q \cdot v\)
余弦相似度：\(sim(q, v) = \frac{q \cdot v}{||q||_2 ||v||_2}\)

这几个相似度在特殊情形下是等价的，其实也是为了处理“相似”而产生的不同做法，本质上相同。

比如，在向量已经归一化的情形下（归一化：\(||v||_2 = 1\)），内积相似度、余弦相似度和 \(L2\) 相似度本质上是相同的

内积相似度和余弦相似度的等价比较好理解，对于 \(L2\) 相似度： \[ ||q-v||_2^2 = ||q||_2^2 + ||v||_2^2 - 2 q \cdot v = 2 - 2 q \cdot v \]

向量检索算法的发展

为了方便，记 \(|\mathcal{B}|=n\)，\(d\) 为向量的维度，\(c\) 为编码压缩率，\(k\) 为空间划分的个数

暴力匹配

暴力匹配（Brute-Force Search）是最简单直接的向量检索方法，它通过计算查询向量 \(q\) 与数据集中每个向量 \(v_i\) 的相似度，找到最相似的 \(K\) 个向量，时间复杂度为 \(O(n \cdot d)\)

但在实际生产中，往往不需要如此精确的数据，可以通过近似算法在更短时间内获得足够好的结果，这就引出了近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）

量化

由于高维向量的存储和计算成本较高，量化（Quantization）技术被引入以减少存储空间和加速计算

量化的意思是将高维向量映射到一个较小的离散空间中，从而减少存储需求和计算复杂度

常见的量化方法包括：\(PQ\)，\(SQ\)

以上的量化方法受到了数据分布的影响，无法估计出精确的误差下界

\(2024\) 年，提出了 \(RaBitQ\) 量化，准确的估计了量化误差下界，并且速度和 \(PQ\)，\(SQ\) 近似

空间划分算法

空间划分算法通过将数据空间划分为多个区域，从而减少搜索空间，提高检索效率

KD 树

KD 树是一种空间划分方法，它通过递归地将数据空间划分为超平面，构建一棵二叉树，从而实现高效的近邻搜索

IVF

IVF （Inverted File）倒排索引是一种常用的空间划分方法，它通过聚类算法将数据集划分为多个簇，并为每个簇建立倒排索引

倒排索引算法具有优秀的性能，Faiss 库中实现的倒排算法结合了倒排索引和量化技术，显著提高了向量检索的效率，在 ANNBenchmarks 中表现出色

图匹配

图匹配是现在向量匹配发展的研究方向

主要的思路是将数据集中的向量表示为图中的节点，节点之间的边表示向量之间的相似度关系，下面介绍目前主流和经典的图匹配算法

NSW

NSW（Navigable Small World）图是一种基于小世界网络理论的近邻搜索算法

算法主要逻辑是把所有向量组织成一个小世界图结构，通过在图中进行贪心搜索来找到近邻

HNSW

HNSW（Hierarchical Navigable Small World）图是 NSW 的改进版本，它引入了层次结构，将图划分为多个层次，从而提高搜索效率

算法的主要逻辑是在不同层次上进行搜索，逐层缩小搜索范围，最终在底层找到近邻

一开始，认为 HNSW 对 NSW 的改进主要体现在引入了层次结构上，也就是所说的跳表，但深入研究会发现，HNSW 的层次结构实际上并未带来显著的性能提升，反而是 HNSW 在图构建和连接策略上的优化才是其性能提升的关键

NGT

NGT 是日本雅虎开源的向量检索库，核心算法基于 NSW，后续在度方面做出了多处优化

NSG

NSG（Navigable Small World Graph）是一种基于小世界网络理论的近邻搜索算法，目前主要使用该算法的开源库有 nmslib 和 pynsg

他是在 HNSW 的基础上进行改进的，主要优化了图的构建和连接策略，HNSW 在构建图时，使用了启发式方法来选择连接边，而 NSG 的入口点是固定的。

NSG 的选边策略实际上和 HNSW 是一致的

Vamana

Vamana 实际上是在 HNSW 建图算法的基础上添加了一个参数 \[\alpha\]，当 \(\alpha = 1\) 时，实际就为 HNSW 选边，但 Vamana 取不同的 \(\alpha\) 值进行了两次选边

DiskANN

DiskANN 是微软提出的一种基于磁盘存储的近邻搜索算法，主要用于处理大规模数据集

HNSW 基础实现

值得一提的是，原论文启发式选边算法中有一个小错误

(´-ω-｀)