更加可靠和有效的近似最近邻搜索|SIGMOD 2023

随机向量投影过程

给定一个对象 x，我们首先对 x（向量） 应用一个随机正交矩阵 𝑃' ∈ R 𝐷×𝐷，然后对其上的𝑑行进行采样(为简单起见，使用前𝑑行)。

结果表示为(𝑃' x)|[1,2，…，𝑑]。

我们将转换后的向量表示为  y := 𝑃′x

基于采样的维度，我们可以计算出 x 的近似距离，表示为 dist'

其中 d 是采样的维度数量。值得注意的是，基于采样维度计算近似距离的时间复杂度为 O(d)。

假设检验寻找合适 d

待解决问题：如何确定需要采样多少个 y 的维度，才能对距离比较操作（DCOs）做出足够自信的结论（即是否决定 𝑑𝑖𝑠 ≤ 𝑟）

假设检验的步骤：

（1）定义一个零假设 H0: dis ≤ r 和它的备择假设 H1: dis > r。

（2）使用 𝑑𝑖𝑠′ 作为 𝑑𝑖𝑠 的估计器。

注意：𝑑𝑖𝑠′ 与 𝑑𝑖𝑠 之间的关系由引理 3.1（欧几里得范数存在一个误差概率） 提供（即：𝑑𝑖𝑠′ 与 𝑑𝑖𝑠 之间的差异受到 𝜖·𝑑𝑖𝑠 的限制，且失败概率最多为 2 exp(−𝑐0𝑑𝜖^2))。

（3）设置显著性水平 p（置信区间）

其中，c0 为常数，其中𝜖是一个需要根据经验调整的参数。

（4）我们检查事件是否发生 （如下图公式）。如果发生，我们可以拒绝𝐻0并以足够的置信度得出结论𝐻1: 𝑑𝑖𝑠> 𝑟；否则我们不能。

假设检验的结果：

情况1：我们拒绝假设H0（即我们得出结论 𝑑𝑖𝑠 > 𝑟），且 𝑑 < 𝐷。在这种情况下，时间成本（主要用于评估近似距离）为 𝑂(𝑑)，小于计算真实距离的时间成本为 𝑂(𝐷)。

情况2：我们无法拒绝假设且 𝑑 < 𝐷。在这种情况下，我们将继续逐步采样y的一些更多的维度，并进行另一次假设检验。（增加d值）

情况3：𝑑 = 𝐷。在这种情况下，我们已经对 y 的所有维度进行了采样，基于采样向量的近似距离等于真实距离。

因此，我们可以进行精确的 DCOs。我们注意到，具有（可能是顺序的）假设检验的增量维度采样过程的时间成本严格小于 𝑂（𝐷）（当它在 Case 1终止时），并且等于𝑂（𝐷）（当它在 Case 3终止时）。

参数𝜖0：

参数𝜖0 是 ADSampling 算法的一个关键参数，因为它直接控制了准确性和效率之间的权衡(𝜖0 越大意味着假设检验的显著性值越小，这进一步意味着假设检验的结果越准确)。

下图绘制了 HNSW++(左图)和 IVF++(右图)在不同 𝜖0 下的 QPS-recall 曲线。总的来说，我们从图中观察到，𝜖0 越大，QPS -召回曲线就会向右下移动。这是因为较大的 𝜖0 以效率为代价可以获得更好的准确性。

我们观察到，当 𝜖0 = 2.1时，精度损失很小，而进一步增加 𝜖0 则会降低效率。因此，为了提高效率而不损失太多的准确性，我们建议将 𝜖0 设置在2.1左右。

参数Δ𝑑 = 32：

在 ADSampling 中，它增量地对数据向量的一些维度进行采样，并在迭代中执行假设测试。为了避免频繁假设测试的开销，我们在每次迭代中对 Δ𝑑 维度进行采样。默认情况下，我们设置 Δ𝑑= 32。

ADSampling算法流程：

Input : A transformed data vector o′, a transformed queryvector q′and a distance threshold 𝑟

输入：一个经过变换的数据向量 o'，一个经过变换的查询向量 q' 和一个距离阈值 𝑟

Output : The result of DCO (i.e., whether 𝑑𝑖𝑠 ≤ 𝑟): 1 meansyes and 0 means no; In case of the result of 1, anexact distance is also returned

输出：DCOs 的结果（即是否 𝑑𝑖𝑠≤𝑟）：1表示是，0表示否；如果结果为1，则还返回一个确切的距离

Initialize the number of sampled dimensions 𝑑 to be 0

将采样维度的数量 𝑑 初始化为 0

    while 𝑑 < 𝐷 do

    Sample some more dimensions 𝑦𝑖incrementally with

    逐步采样一些维度𝑦𝑖

    𝑦𝑖 = o𝑖′ − q𝑖′

    Update 𝑑 and the approximate distance 𝑑𝑖𝑠′accordingly

    相应地更新 𝑑 和近似距离 𝑑𝑖𝑠′

    Conduct a hypothesis testing with the null hypothesis𝐻0 as 𝑑𝑖𝑠 ≤ 𝑟 based on the approximate distance 𝑑𝑖𝑠′

    进行零假设检验，零假设为 𝑑𝑖𝑠 ≤ 𝑟，检验基于近似距离 𝑑𝑖𝑠′。

    if 𝐻0 is rejected and 𝑑 < 𝐷 then Case 1

      return 0

    else if 𝐻0 is not rejected and 𝑑 < 𝐷 then Case 2

      Continue

    else Case 3

      return 1 (and 𝑑𝑖𝑠′) if 𝑑𝑖𝑠′ ≤ 𝑟 and 0 otherwise

注意：当 ADSampling 在 Case 3（即𝑑 = 𝐷）终止时，将不会出现失败，因为在这种情况下，近似距离 𝑑𝑖𝑠′ 等于真实距离 𝑑𝑖𝑠，DCO结果是精确的。当ADSampling在Case 1终止时，如果 𝑑𝑖𝑠 ≤ 𝑟 成立，则会发生失败，因为在这种情况下，它得出了 𝑑𝑖𝑠 > 𝑟（通过拒绝零假设）。

HNSW++

1、HNSW+：

概念：维护了一个 max-heap 大小为 𝑁（𝑒𝑓）的结果集 R，并将距离作为键，其中 𝑁（𝑒𝑓）>𝐾。对于每个新生成的候选对象，它会检查其距离是否不大于集合 R 中最大距离（的对象），如果是，则将对象插入集合 R。

具体操作：使用 ADSampling 对每个候选对象进行 DCOs，其中 R 中距离最大的对象作为阈值距离。

R集的两个作用：

1、维护了到目前为止生成的候选对象中距离最小的 KNN。这些 KNN 将在算法结束时作为输出返回。

2、维护了到目前为止生成的候选对象中的前 𝑁^(th) ef 个最大距离。这个距离被用作 DCO 的阈值距离，影响候选对象的生成。

具体来说，如果由 HNSW+ 生成的候选对象的距离小于等于 R 中的第 Nef 大距离，则它将被添加到搜索集 S 中进行进一步的候选对象生成。对于每个新生成的候选对象，它会检查其距离是否不大于集合R中最大距离（的对象），如果是，则将对象插入集合R。

2、HNSW++：

概念：通过维护两个集合 R1 和 R2 来解耦 R 的两个作用，即为每个作用维护一个集合。

集合 R 的分解：

集合 R1 的大小为 K，基于精确距离（深绿色）。

集合 R2 具有大小 𝑁𝑒𝑓，并基于距离，这些距离可以是精确的或近似的。

具体来说，对于每个新生成的候选对象，他都会检查它的距离是否小于或等于集合R1中最大距离，并在满足条件时将该候选对象插入到集合 R1 中。

注：这个 DCO 会产生一个副产品，即观察到的距离 𝑑𝑖𝑠'（浅绿色），当 ADSampling 终止时，它可以是精确的（如果所有的 D 个维度都被采样），或者是近似的（如果它以 𝑑<𝐷 的方式终止）。然后，它根据观察到的距离类似于 HNSW+ 维护集合 R2 和集合 S。

总结：HNSW++ 使用的是K作为寻找候选值；HNSW+ 使用 𝑁𝑒𝑓 寻找候选值。其中 𝑁𝑒𝑓 > K。

IVF++

1、IVF：

在原始的 IVF 算法中，同一簇中的向量按顺序存储。在评估它们的距离时，算法按顺序扫描所有这些向量的维度，这展现出强烈的局部性，并因此使其具有良好的缓存性能。

2、IVF+：

它扫描的维度比 IVF 少，但如果使用相同的数据布局，它就无法具有良好的缓存性能。具体来说，当 IVF+ 为数据向量终止维度采样过程时，随后的维度可能已经从主存储器加载到缓存中，尽管它们不是必需的。

3、IVF++：

ADSampling 一定会先采样一些维度（如 𝑑1 个），然后根据假设检验结果逐渐采样更多维度。也就是说，每个候选向量的前 𝑑1 个维度一定会被访问。出于这个原因，我们将所有候选向量的前 𝑑1 个维度顺序存储在一个数组 𝐴1 中，将所有候选向量的其余 𝐷−𝑑1 个维度顺序存储在另一个数组 𝐴2 中。

召回率：成功检索到的真实 knn 的数量与 𝐾 之间的比率。

平均距离比：检索到的 𝐾 对象与真实 knn 的距离比。

结论总结：

结论 1（结果图）：

我们可以清楚地观察到 AKNN+ 和 AKNN++ 在达到几乎相同的召回率的情况下，评估的维度比 AKNN 少得多。

具体而言，在 GIST 上，对于 𝑁𝑒𝑓 的所有测试值，HNSW+ 和 HNSW++(相对于 HNSW)的精度损失不超过0.14%，IVF+ 和 IVF++ 的精度损失不超过0.1%。

与此同时，HNSW++ 组在总维度上从39.4%节省到75.3%，HNSW+ 组从34.5%节省到39.4%，IVF+/IVF++ 组从76.5%节省到89.2%。

基线法 HNSW* 从10.9%节省到15.7%，这解释了它在 HNSW 上的改善很小。IVF*/IVF** 可节省28.9%至40.4%。

结论 2：

技术在 IVF 上比 HNSW 带来了更多的改进(即使 IVF 比 HNSW 表现更好，例如在 Word2Vec 上)。

原因：HNSW 的 DCOs 以外的其他计算比IVF的计算更重(如下图所示)

结论 3：

该技术总体上在高精度区域比低精度区域带来了更多的改进(例如，GIST 95% vs . 85%)

原因：当 AKNN 算法以更高的精度为目标时，它不可避免地会生成更多低质量的候选对象，并且距离差距更大 𝛼，因此它需要更少的维度来获得可靠的 DCOs。

结论 4：

数据布局优化对 IVF+(即 IVF++ vs . IVF+)的改进大于对 IVF*(即 IVF** vs . IVF*)的改进。

原因：ADSampling 具有对数复杂度，而基线 PDScanning 具有线性复杂度。具体来说，在使用 ADSampling 时，第一个 Δ𝑑 维度对于许多 dco 已经足够，因此可以避免对图4c 中第二个数组 𝐴2 的多次访问。当对 DCOs 使用 PDScanning 时，它仍然会频繁地访问第二个数组，因为它需要的维度超过 Δ𝑑。