了解如何结合两个基本的相似性搜索索引以发挥两者的优势

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在本系列的前两部分中，我们讨论了信息检索中的两种基本算法：倒排文件索引和乘积量化。它们都优化了搜索性能，但侧重于不同的方面：第一个加速了搜索速度，而后者将向量压缩为更小的、节省内存的表示形式。

由于两种算法侧重于不同的方面，自然出现的问题是是否可以将这两种算法合并为一种新算法

在本文中，我们将结合这两种方法的优点来产生快速且内存高效的算法。作为参考，大多数讨论的想法都将基于本文。

在深入研究细节之前，有必要了解残差向量(residual vectors)是什么，并对它们的有用属性有一个简单的直觉。稍后我们将在设计算法时使用它们。

残差向量(Residual vectors)

想象一下执行了一个聚类算法并产生了多个聚类。每个簇都有一个质心和与其关联的点。残差residual是点(向量)与其质心的偏移量。基本上，要找到特定向量的残差，必须从向量的质心中减去该向量。

如果聚类是通过 k-means 算法构建的，则聚类质心是属于该聚类的所有点的平均值。因此，从任意点找到残差相当于从中减去簇的平均值。通过从属于特定簇的所有点中减去平均值，这些点将以 0 为中心。

原始点簇显示在左侧。然后从所有聚类点中减去聚类质心。生成的残差向量显示在右侧。

我们可以观察到一个有用的事实：

用残差替换原始向量不会改变它们之间的相对位置。

也就是说，向量之间的距离始终保持不变。让我们简单地看一下下面的两个方程。

减去平均值不会改变相对距离

第一个方程是一对向量之间的欧氏距离公式。在第二个方程中，从两个向量中减去簇平均值。我们可以看到均值项简单地被抵消了——整个表达式变得与第一个方程中的欧几里得距离相同！

我们通过使用 L2 度量（欧氏距离）公式证明了这一说法。重要的是要记住，此规则可能不适用于其他度量方法。

因此，如果对于给定的查询，目标是找到最近的邻居，则可以仅从查询中减去簇均值，然后继续在残差中进行正常的搜索过程。

从查询中减去平均值不会改变其与其他向量的相对位置

现在让我们看一下下图中的另一个示例，其中有两个簇，其中每个簇向量的残差是单独计算的。

从簇的每个向量中减去相应质心的平均值将使所有数据集向量以 0 为中心。

这是一个有用的观察结果，将来会用到。此外，对于给定的查询，我们可以计算所有集群的查询残差。查询残差允许我们计算到簇的原始残差的距离。

从每个簇中减去平均值后，所有点都以 0 为中心。查询和查询残差与相应簇的其他点的相对位置不会改变。

训练(Training)

考虑到上一节中有用的观察结果后，我们可以开始设计算法。

给定一个向量数据库，构建一个倒排文件索引，将向量集划分为n个Voronoi 分区，从而减少推理查询过程中的搜索范围。

在每个 Voronoi 分区内，从每个向量中减去质心的坐标。结果，来自所有分区的向量变得彼此更接近并且以 0 为中心。此时，不需要原始向量，因为我们存储它们的残差。

之后，对来自所有分区的向量运行乘积量化算法。

重要的方面：乘积量化不是针对每个分区单独执行的——这会降低效率，因为分区的数量通常很高，这可能会导致需要大量内存来存储所有代码本。相反，该算法是同时对所有分区的所有残差执行的。

实际上，现在每个子空间都包含来自不同 Voronoi 分区的子向量。然后，对于每个子空间，像往常一样执行聚类算法并构建k个聚类及其质心。

训练流程

用向量的残差替换向量的重要性是什么？如果向量不被它们的残差替换，那么每个子空间将包含更多不同的子向量（因为子空间将存储来自不同的非相交 Voronoi 分区的子向量，这些分区在空间中可能彼此相距很远）。现在，来自不同分区的向量（残差）相互重叠。由于现在每个子空间的多样性较少，因此有效表示向量所需的再现值较少。换句话说：

在与之前使用的相同长度的PQ码的情况下，向量可以更准确地表示，因为它们具有较小的方差。

推理查询(Inference)

对于给定的查询，找到 Voronoi 分区的k个最近的质心。这些区域内的所有点都被视为候选点。由于原始向量最初被每个 Voronoi 区域中的残差替换，因此还需要计算查询向量的残差。在这种情况下，需要为每个 Voronoi 分区单独计算查询残差（因为每个区域具有不同的质心）。只有所选 Voronoi 分区的残差才会分配给候选者。

然后将查询残差分割成子向量。与原始乘积量化算法一样，对于每个子空间，计算包含从子空间质心到查询子向量的距离的距离矩阵d。必须记住，每个 Voronoi 分区的查询残差都是不同的。基本上，这意味着需要为每个查询残差单独计算距离矩阵d。这是所需优化的计算成本。

最后，像之前在乘积量化算法中所做的那样，对部分距离进行求和。

排序结果(Sorting results)

计算完所有距离后，需要选择k个最近邻。为了有效地做到这一点，作者建议维护MaxHeap (注：容量为k 的大顶堆用于查最小最近的k个值，小顶堆则相反)数据结构。它的容量有限为k，并且在每一步中，它存储k个当前最小距离。每当计算新距离时，仅当计算值小于 MaxHeap 中的最大值时，才会将其值添加到 MaxHeap 中。计算完所有距离后，查询的答案已存储在 MaxHeap 中。使用 MaxHeap 的优点是其快速构建时间为线性时间O(n) 。（注：高度 h=logn；2^h -h -1 = n - logn -1 => O(n)）