ANN搜索
向量数据库在LLM等领域中的应用已经比较广泛，而ANN（Approximate Nearest Neighbor，近似最近邻）搜索是向量数据库的核心技术之一，这里简单介绍下ANN搜索的基本原理和常用算法。
什么是ANN搜索¶
ANN搜索本质上就是要从海量高维向量中，快速找到目标向量的临近向量。 由于高维空间的“维度灾难”问题，传统的精确最近邻搜索（Exact Nearest Neighbor，ENN）在高维空间中效率非常低下，因此ANN搜索通过牺牲部分精度来换取更高的搜索效率。
常用的ANN算法¶
要实现快速搜索，常见的思路有：树、LSH、量化、IVF、图等。
基于树的算法¶
KD-Tree¶
构建¶
- 选择一个维度作为划分维度，通常选择方差最大的维度。
- 选择该维度的中位数作为划分点，将数据集划分为两部分，左侧小于中位数，右侧大于中位数。
- 递归对左右子集进行上述划分，直到满足停止条件（如节点包含的数据点数小于某个阈值）。
检索¶
- 从根节点开始，比较目标向量与当前节点的划分维度值，决定向左还是向右子树继续搜索。
- 当到达叶节点时，将节点加入候选集，若候选集大小超过K，淘汰距离最远的点（可能是当前节点）。
- 回退到父节点，如果是根节点，结束搜索；否则，将当前节点加入候选集，若候选集大小超过K，淘汰距离最远的点。
- 计算目标向量与划分维度的距离，如果该距离小于候选集中的最远距离，或者候选集不足K，说明另一侧子树可能包含合适的点，对该子树进行搜索（若存在）；否则继续回退。
应用¶
适用于中低维数据，通过递归划分空间来构建树结构，查询时通过遍历树来找到近邻。
Ball Tree¶
构建¶
检索¶
应用¶
LSH¶
LSH基于这样一个前提：
相似的向量在经过合适的hash映射后，仍然会映射到相同的桶中的概率较高，而不相似的向量映射到相同桶中的概率较低。
构建¶
- 选择N个合适的hash函数，通常N较小（如10-20）。
- 对每个向量计算N个hash值，组合成一个N维的hash向量。
- 将具有相同hash向量的向量存储在同一个桶中，形成倒排索引。
检索¶
- 对目标向量计算N个hash值，得到其hash向量。
- 找到与目标向量hash向量相同或相似的桶，收集这些桶中最近的K个向量作为结果。
量化¶
Product Quantization（PQ）¶
将高维向量分割成多个子向量，并对每个子向量进行量化，从而减少存储空间和计算复杂度。
Optimized Product Quantization（OPQ）¶
在PQ的基础上进行优化，提高搜索精度。
IVF¶
将向量空间划分为多个簇，每个簇对应一个倒排列表，查询时先找到目标向量所属的簇，然后在该簇内进行精确搜索。
基于图的算法¶
HNSW¶
构建一个多层次的小世界图，通过图的导航来实现快速近邻搜索。
NSW¶
类似HNSW，但结构更简单，适用于动态数据。