向量检索算法

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

近似检索

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

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

• 向量量化的编码算法

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