向量检索算法综述
目录
1. 基于树的搜索
2. 基于哈希的空间划分
3. 基于图的搜索
3.1 朴素想法
3.2 NSW
3.3 HNSW
3.4 小结
4. 基于量化的编码
4.1 SQ和PQ
4.2 IVFPQ
4.3 小结
5 总结
Reference
时代的浪潮使得海量数据呈现出爆发式的增长态势，在这一背景下向量检索技术的应用范围不断扩大。
其中不仅包括但不限于图片推荐、视频推荐等多媒体领域，
而且也涵盖了文章去重、以图搜图等多个应用场景。
这些应用共有的显著特点在于处理的数据规模巨大且维度高度复杂。
因此，在速度和存储能力方面，
传统的精确线性搜索都难以满足现代需求。
正是基于这种背景下，
近邻搜索技术应运而生并迅速崛起于这一领域，
展现出独特的技术魅力与价值。
近邻搜索即阐述其基本原理：尽量缩小数据集的覆盖范围以加快数据检索效率。目前业界普遍采用的近邻搜索算法主要包括四种主要类型，在本文中将分别介绍每种类型代表性的算法方案。
- 基于树状结构的索引（Annoy、KD-Tree）
- 通过哈希函数实现的空间划分（LSH）
- 利用图结构构建的索引（NSW、HNSW）
- 通过量化方法实现的数据压缩（SQ、PQ）
1. 基于树的搜索
基于树的方法通过树结构实现空间划分，在这种框架下,KD-Tree和Annoy被认为是两种具有代表性的重要算法. 在每次分割过程中,KD-Tree会选择具有最大方差的那个维度,并在此维度上完成分割.
本文以Annoy为例对基于树的搜索进行详细阐述。
Annoy 是Spotify用于音乐推荐的向量检索算法库，在github上开源。
Annoy持续地通过超平面将向量空间进行分割直至每个子空间中的样本数量少于设定值这一系列的分割步骤与二叉树中父节点向左右子节点延伸的过程具有相似性而该超平面由KMeans聚类算法（参数k=2）生成两个质心点并取这两点连线上的法平面作为该超平面
如此...直到：
整个过程类似如下的二叉树：
自根节点出发展开查询流程，在每一步骤中若当前访问的某一个节点发现该节点的分支数量少于预设的搜索阈值，则算法在此处终止探索。
这样的查找存在以下问题：首先，在某一个节点处，该节点所包含的向量数量不足于满足所需查询的近邻数量；其次，在某些情况下，原本相邻且较近的节点可能会被分配到不同的子树中，从而导致搜索精度受到影响。
对于第一点的参数设置来说，在处理到某个节点时，可以通过将相邻的所有子节点依次加入队列中，并在后续步骤中确保这些子节点所包含的所有向量都被遍历。
对于第二点，可以构造多棵树，从而避免一棵树造成的随机性。
总结一下，Annoy的优缺点
优点：
- 包含以下几种常见的度量方式：欧几里得距离、曼哈顿距离、余弦相似度以及海明空间。
- 独立实现索引与向量检索功能，并使索引能够在同一个节点上被多个进程共享。
缺点：
- 适用于维度较低且数据规模较小的向量检索场景
- 为提升模型准确率需构建多棵决策树
- 当前仅支持非负整数类型的ID编码 若采用其他类型ID则需自行维护对应映射关系
2. 基于哈希的空间划分
LSH：基于哈希冲突的概率，在适当选择一组哈希函数的情况下，在相似度较高的向量之间提高映射到同一cell中的可能性。当处理查询时，在对应的cell中搜索相关向量以减少搜索范围。
3. 基于图的搜索
3.1 朴素想法
图形，由于其本身保留相邻信息，在向量检索中具有高效的检索能力。让我们从一张简单的图表开始
为了寻找那个粉红色且距离目标最近的点，请选择任意一点作为起点，并选取标记为A的那个。随后，在其邻近节点(B、C、D)中找出与目标最接近的那个节点D。接着，在D相邻节点(F、J、E)中确定最接近的目标为E。在检查E的所有邻接节点时发现其已经是距离目标最近的情况后搜索终止
朴素想法很简单，但是有如下几个问题：
- 存在一些节点无法直接获取相关信息。
- 当两个相近的节点之间没有直接连接关系时, 可能会影响整体系统的运行效率, 例如节点E与节点L之间就不存在直接连接。
- 一个节点所需的邻居数量会影响资源消耗. 当数量较多时会占用更多存储空间; 然而数量过少可能导致网络性能下降.
3.2 NSW
针对朴素想法的几个问题，我们采取如下措施：
有些点无法查询 ===> 要求构图时所有的点必须有相邻的点
如果两个相近的点无连线，则影响效率 ===>构图时相邻的点必须有连线
需要多少个友点 ===> 作为参数由用户指定
针对上述问题，在查询效率方面尚未取得明显提升的情况下
图中标注为红色的就是高速公路。当从entry point进行查找时，无需考虑这些较近的节点。
NSW在这种情况下应运而生，在构建网络拓扑的过程中，在某个新节点插入时会搜索到离该新节点最近的m个现有节点（其中参数m由用户设定），随后会对新节点与其关联的所有现有节点进行连接操作。这种情况下，在早期被插入的新节点往往具有较高的可能性拥有高速公路功能；然而，在后续构造过程中可能会有更多的节点被插入到该区域中来，在这种情况下之前建立起来的一些原有连线则很可能成为高速公路上
3.3 HNSW
NSW对图的数据查找采用了高速路机制提高了效率。但这种高速路存在一定的不确定性，并且在插入越后的点时获得概率就越低。那么这里借鉴了跳表的设计思路，在Redis中作为有序列表的基础数据存储方式优化链表查询速度。通过随机分配层数构建多层链式结构来实现高效搜索，并将每一层视为独立链表构建出一个多级快速访问路径，在搜索时优先从高阶路径开始寻找目标节点。
HNSW的思路类似：
按照上图所示的结构进行构建，在需要插入新节点时将新节点首先放置在最低层，并随机选择一层作为该新节点所属的层数；然后依次在每一层往上添加该节点以完成构图；其中每一层的具体连接方式均遵循NSW算法的思想。这种层级化的连接方式使得高层节点之间的联系如同快速通道；而搜索过程则从顶层开始逐步向下探索以实现高效定位。
3.4 小结
优点：
- 召回率高，检索快（在ANN Benchmark中HNSW的查询最快）
缺点：
- 训练时间长（构图）
- 存储成本较高（图的关系）
4. 基于量化的编码
4.1 SQ和PQ
在量化方法中包含两种主要类型：SQ与PQ。SQ通过将单个维度的数据转换为指定精度的一个数值来实现这一目标，并且通常会伴随着一定精度上的损失以换取更低的数据存储开销。例如，在处理32位整型数据时（如图所示），将其压缩至8位整型会是一个典型的应用场景。相比之下，在PQ方法中，则会将整个向量分割为M个子块，并对每个子块同样采用指定精度进行数据压缩。例如，在实际应用中（如图所示），128维空间中的每个样本（每个维度占用32位）会被分割为4个子空间，并对每一组子空间进行独立压缩处理以减少整体数据规模。因此，在这种情况下，原始128维的数据可以通过4维（每维占用8位）的新表示来进行高效处理，并且这种降维后的表示仍然能够保留足够的信息特征用于后续分析工作
当一个查询向量到达时
4.2 IVFPQ
IVFPQ是一种基于粗粒化量化的方法，在处理过程中首先对数据进行粗粒化量化处理。接着，在这些聚类中进行PQ编码过程。具体过程如下：
对样本空间进行粗量化处理后，在1024个预定义的高维码本库中选择一个最优基底簇。通过计算所有样本与各基底簇之间的距离度量值（即残差），找到与每个样本最接近的基底簇，并确定属于各个基底簇下的样本数量。从而确定属于各个基底簇下的具体样本人数。对于整个样本空间而言，在完成上述步骤后即可完成一次完整的分段K均值迭代过程。对于后续查询操作而言，则是采用的方法与IVF-PQ方案相似：首先将查询向量进行量化处理以确定其所属的基底簇，并识别出需要进一步处理的对象簇。随后针对这些对象簇仅需修改对应的数学表达式部分。
4.3 小结
SQ和PQ通过量化压缩的方式存储向量，并基于到聚类中心的距离优化真实的距离以减少计算次数。同时结合了IVF技术对PQ的空间进行限制，在进一步缩小了搜索空间的基础上显著提升了搜索效率。
5 总结
在分析了多种算法后发现，在基于图的算法中表现更为出色，并且在ANN基准测试中取得了最优成绩。然而由于构建图结构的时间较长以及记录各节点之间连接的信息需求较高，在存储资源上存在较大压力。相比之下SQ和PQ通过对向量进行压缩处理从而有效地降低了存储空间的需求。
开发者创建了一个名为ANN Benchmark的功能包，并提供了一系列向量检索算法的基准测试以及一系列数据集。这些资源方便地供用户参考或直接运行自己的版本以进行比较研究。
以下选取两个欧氏距离的数据集Benchmark结果图：
fashion-mnist-784-euclidean(k=10):
sift-128-euclidean(k=10):
从以上两图可以看出：
- 基于图的算法中，如hnsw和NGT等方法表现优异
- 同一类型的核心原理下不同具体实现可能会带来显著性能差异；例如使用faiss库实现的和nmslib库实现的两种hnsw变体
Reference
深入解析HNSW算法的起源与发展及其构成要素