向量检索算法

通常来说，面向向量的相似性检索的方法分成：精确检索和近似检索两类。而精确检索的本质就是线性查找。

线性查找

通过在整个向量空间内，遍历所有已存向量计算其与检索向量的距离，通常是计算欧几里德距离或者点积。欧式距离最近的向量或者点积最大的向量就是相似度最高的向量。线性查找算法简单，不需要建立额外的数据结构和存储空间，通过使用例如 Intel 架构下的 MKL 或者使用 NVIDIA GPU 的 cublas 等并行计算库加速，对于中小规模的向量集的相似性检索是合适的。但是，由于线性查找的时间复杂度是 O(Nd)，其中 N 是向量集的规模，d 是向量的维度，随着向量集的规模的增大或者向量维度的增加，线性查找就会显得力不从心。

近似检索

所谓近似检索，就是通过聚类、降维或者编码等方式，将原来需要在全量高维向量空间内的搜索，转换为在小范围空间或者相对低维的向量空间内搜索的算法。这类算法的特点是，检索的时间复杂度小于 O(Nd)，但是真正用来搜索之前，需要用一个向量分布类似的一个训练集来训练，获得一个产生合理数据划分或者编码的模型。然后再利用这个模型，使用额外的存储空间，建立对全量高维向量的索引。目前近似检索的算法，通常分为：基于树的搜索算法，基于哈希的空间划分法和向量量化的编码法。

• 基于树的搜索算法

  基于树的搜索方法通常根据向量的分布特征采用一系列的超平面将高维向量空间划分为多个子空间，并采用树型结构维护空间划分的层次关系。树中的每一个非叶子节点对应于一个子空间和一组超平面。超平面将该节点的子空间进一步划分为更小的子空间，每一个子空间与该节点的一个孩子节点相对应。由此，树中的根节点对应的是完整的向量空间，除根节点之外的每一个节点均对应于其父节点空间被划分后得到的一个子空间。而每个叶子节点对应于一个不可再分的子空间。依据上述规则，对于向量集合中的各个向量都可以找到树中的一个叶子节点与之对应。在向量搜索的过程中，可通过树型结构快速的搜索到若干个距离目标向量较近的叶子节点。通过依次计算目标向量与上述叶子节点所对应各向量的距离即可近似得到与目标向量最相似的向量。 采用基于树的搜索方法可以快速的定位到与目标向量最为相似的若干个叶子节点，从而有效地避免了很多无效比对，提高了搜索效率。然而，随着向量维度的提高，计算用于划分空间的超平面的开销将显著增大，从而影响树型结构的构建效率。此外，如果目标向量与某一超平面距离较近，该方法的搜索结果可能会丢失大量的与目标相似的向量，从而影响查询的准确度。

• 基于哈希的空间划分法

  基于哈希的搜索方法采用一组局部敏感哈希函数对向量集合进行划分。通过采用局部敏感哈希函数可以对每一个向量计算出一个与之相对应的哈希值。对于距离较接近的向量，其哈希值也较为接近。该方法将各局部敏感哈希函数的值域划分为若干个区间，从而每个向量相应于特定的局部敏感哈希函数，均有一个区间与之对应。该方法通过哈希值的区间对向量进行划分，若两向量对于任一哈希函数其哈希值所在的区间均相同，则这两个向量属于同一分类。在搜索时，通过相同的局部敏感哈希函数和区间划分方法可以计算得到目标向量所属分类。然后可依次计算该分类以及该分类的邻近分类中所有向量与目标向量的距离获取距离最小的向量。 基于哈希的方法，通过计算目标向量所在分类以及邻近的分类可以有效的排除掉大量与目标向量相似度较低的向量，减少了向量相似度的计算次数。但是，该方法通常只能对向量空间进行均匀划分，而实际应用中向量在空间中的分布通常是不均匀的，从而导致各个分类中向量的数量相差巨大，并进一步影响搜索的效率和准确度。

• 向量量化的编码算法

  基于向量量化的方法通常采用聚类的方式对向量集合中的向量进行划分。该方法通过 k-means 等聚类方法将向量集合划分为多个聚类，并记录各个聚类的中心点的坐标。在向量搜索时，首先依次比对目标向量与各个聚类中心的距离，选择出与目标向量最为接近的若干个聚类中心。接下来获取这些聚类中心所对应聚类中的所有向量，依次计算各向量与目标向量的距离，选择出距离最为接近的若干个向量。 该方法采用聚类的方法将数据集合划分，从而在搜索过程中排除掉与目标向量相似度较低的向量。然而，该方法在高维向量的搜索中容易遗漏部分潜在的与目标向量距离较近的向量，从而难以达到较高的准确度。

• 基于图的搜索方法

  与以上方法不同，基于图的搜索方法通常不对向量空间进行划分。该方法预先计算向量集合中各向量间的相似度，并以图的形式维护向量之间的相似关系。具体而言，在图中每个向量是一个节点，距离较近的节点之间通过边相互连接。在搜索时，从一个或者多个起始节点出发进行探索。每次探索一个节点时，计算该节点的所有邻居节点与目标向量的相似度，并基于当前探索的结果，选择与目标向量最为相似且未被探索的节点作为下一次需要探索的节点并开始下一次探索。以上过程在无法找到新的探索节点时结束，并将探索过程中所有被访问的节点中与目标向量最为相似的节点作为搜索结果。 基于图的方法通常有较高的搜索效率和准确度，但是构建搜索图的过程中需要进行大量的向量距离计算，从而导致极大的计算开销。除此之外，在需要向向量集合中增加新的向量时，通常需要对搜索图进行重新构建，从而严重的影响了向量的插入效率。