向量检索简介
目前很多机器学习应用都是基于embedding开展的，这些embedding或者作为下游任务的输入特征，或者存储起来用于相似度查找（如基于相似性的检索）。一般相似性查找都是基于最近邻搜索的方法来寻找相似item，出于效率的考虑，实际中一般都会使用ANN（Approximate Nearest Neighbor）来做这件事。
通常，最近邻搜索问题被定义为：给定空间M中点集S及一个查找点q，找到S中离q最近的点。通常M是一个度量空间，相似性由距离度量（distance metric）来表示，这里的度量通常（不绝对）是对称的且满足三角不等式，常见的度量有欧氏距离、曼哈顿距离、角度距离（余弦相似度）等。
常见的最近邻搜索应用有：
- 模式识别（光学特征）
- 统计分类（KNN算法）
- 计算几何（最近点对问题）
- 数据库（基于内容的图像检索）
- 编码理论（最大似然译码）
- 数据压缩
- 推荐系统
- 拼写检查
- 聚类分析
向量检索方法
精确方法
- 线性搜索 时间复杂度O(dN)，其中N是S的cardinality，d为M的维度。由于无需维护搜索数据机构，所以该方法空间复杂度为常数。对于高维空间上的搜索，该方法一般优于空间分割。
- 空间分割 即分支定界在向量检索的应用，基于不同的空间划分方法产生了不同的算法，其中最简单的是k-d树。k-d树算法迭代地将搜索空间均分为包含父区域的一半点的两个区域，在每个分割点评估请求（query）来遍历这棵树。根据查询中指定的距离，可能包含命中点的邻近分支可能也需要进行评估。对于固定维度的查询时间以及随机分布的点，平均时间复杂度为O(\(logN\))，最差时间复杂度为O(\(kN^{(1 - \frac{1}{k})}\))。R-tree是用于动态场景的最近邻搜索，因为其支持高效的插入与删除操作。在一般度量空间的情况下，分枝定界方法被称为度量树方法。具体的例子包括vp-tree和BK-tree方法。
近似方法
在大多数情况下，使用ANN可以在达到相似查找精确度的情况下大幅提高查找效率。
- 邻域图中的贪心搜索 该方法被认为是目前ANN搜索算法的SOTA，典型代表HNSW（Hierarchical Navigable Small World graphs）。该方法：贪心地遍历邻域图\(G(V,E)\)，图中每个点\(x_i\in S\)都与顶点\(v_i\in V\)唯一关联。基本的贪心算法工作原理如下：搜索从进入点\(v_i\in V\)开始，计算请求点q与该顶点的所有相邻顶点的距离，然后找到具有最小距离值的顶点。如果查询到所选顶点的距离值小于查询到当前元素的距离值，则算法将移动到所选顶点，并将其作为新的进入点。该方法在达到一个局部最小值时停止（某个顶点的所有相邻顶点都不如该顶点与请求点近）。
- 局部敏感哈希 局部敏感散列(LSH，Locality sensitive hashing)是一种基于距离度量将空间中的点进行分桶的技术。在选择的度量下彼此接近的点以高概率被映射到相同的桶。
- 具有小本征维数空间的最近邻搜索 覆盖树（cover tree）有一个基于数据集倍增常数的理论界。搜索时间的上界是O(\(c^{12}logn\))，其中c是数据集的膨胀常数。
- 投影径向搜索 在数据为几何点的密集三维地图的特殊情况下，该传感技术的投影几何可以极大地简化搜索问题。这种方法要求通过向二维网格的投影来组织3D数据，并假设数据在除了对象边界之外的空间上是平滑的。在实际应用于真实世界立体视觉数据时，该技术对于K近邻问题的平均搜索时间为O(1)或O(K)。
- 向量近似文件 树索引结构在高维空间中失效，因为需要检查的节点百分比越来越高。为了加快线性搜索速度，首先使用存储在内存中的特征向量的压缩版本对数据集进行预过滤。在第二阶段，使用磁盘上未压缩的数据来计算距离，从而确定最终的候选对象。
- 基于压缩/聚类搜索 向量近似文件是基于压缩搜索的特例，其中每个特征分量被独立压缩。多维空间中最优压缩技巧是通过聚类实现的向量量化（Vector Quantization）。数据集按照最具有“希望”的簇聚类，相比于基于VA-file、树索引的方法有巨大的提升。
向量检索算法实现
关于各种向量检索算法的性能比较，可以参考ANN benchmark网站，算法的选取需要考虑到recall要求、数据集规模大小（内存是否满足index size要求）、向量维度（尽量降维）、QPS要求，是否有GPU支持（Faiss）等因素。不同的项目有不同的考虑，最终选择还是要基于自己的特定项目做实验测试。发现一个不错的博客，里面有作者做的关于HNSW在约2亿规模、128维向量检索10000条query的测试结果。
