向量检索算法

精确检索的本质就是线性查找。线性查找通过在整个向量空间内，遍历所有已存向量计算其与检索向量的距离，通常是计算欧几里得距离或者点积。欧氏距离最近的向量或者点积最大的向量就是相似度最高的向量。线性查找算法简单，不需要建立额外的数据结构和存储空间。

例如，通过使用例如 Intel 架构下的 MKL 或者使用 NVIDIA GPU 的 cublas 等并行计算库加速，对于中小规模的向量集的相似性检索是合适的。但是，由于线性查找的时间复杂度是 O(Nd)，其中 N 是向量集的规模，d 是向量的维度，随着向量集的规模的增大或者向量维度的增加，线性查找就会显得力不从心。

Milvus 提供了 FLAT 索引类型，可以实现精确检索。

近似检索

目前，近似检索的算法通常分为以下几种：基于树的搜索算法；基于哈希的空间划分法；向量量化的编码算法；基于图的搜索方法。

基于树的搜索方法通常根据向量的分布特征采用一系列的超平面将高维向量空间划分为多个子空间，并采用树型结构维护空间划分的层次关系。树中的每一个非叶子节点对应于一个子空间和一组超平面。超平面将该节点的子空间进一步划分为更小的子空间，每一个子空间与该节点的一个孩子节点相对应。由此，树中的根节点对应的是完整的向量空间，除根节点之外的每一个节点均对应于其父节点空间被划分后得到的一个子空间。而每个叶子节点对应于一个不可再分的子空间。依据上述规则，对于向量集合中的各个向量都可以找到树中的一个叶子节点与之对应。在向量搜索的过程中，可通过树型结构快速的搜索到若干个距离目标向量较近的叶子节点。通过依次计算目标向量与上述叶子节点所对应各向量的距离即可近似得到与目标向量最相似的向量。

采用基于树的搜索方法可以快速的定位到与目标向量最为相似的若干个叶子节点，从而有效地避免了很多无效比对，提高了搜索效率。然而，随着向量维度的提高，计算用于划分空间的超平面的开销将显著增大，从而影响树型结构的构建效率。此外，如果目标向量与某一超平面距离较近，该方法的搜索结果可能会丢失大量的与目标相似的向量，从而影响查询的准确度。

基于哈希的方法，通过计算目标向量所在分类以及邻近的分类可以有效的排除掉大量与目标向量相似度较低的向量，减少了向量相似度的计算次数。但是，该方法通常只能对向量空间进行均匀划分，而实际应用中向量在空间中的分布通常是不均匀的，从而导致各个分类中向量的数量相差巨大，并进一步影响搜索的效率和准确度。

基于向量量化的方法通常采用聚类的方式对向量集合中的向量进行划分。该方法通过 k-means 等聚类方法将向量集合划分为多个聚类，并记录各个聚类的中心点的坐标。在向量搜索时，首先依次比对目标向量与各个聚类中心的距离，选择出与目标向量最为接近的若干个聚类中心。接下来获取这些聚类中心所对应聚类中的所有向量，依次计算各向量与目标向量的距离，选择出距离最为接近的若干个向量。

该方法采用聚类的方法将数据集合划分，从而在搜索过程中排除掉与目标向量相似度较低的向量。然而，该方法在高维向量的搜索中容易遗漏部分潜在的与目标向量距离较近的向量，从而难以达到较高的准确度。

基于图的方法通常有较高的搜索效率和准确度，但是构建搜索图的过程中需要进行大量的向量距离计算，从而导致极大的计算开销。除此之外，在需要向向量集合中增加新的向量时，通常需要对搜索图进行重新构建，从而严重影响了向量的插入效率。