本篇论文来自于SIGMOD 2023，主要工作（1）提出一种随机算法ADSampling; （2）基于ADSampling，开发了两种算法特定的技术作为插件来增强现有的AKNN算法。

背景

提出问题：在高维空间中，几乎所有AKNN算法的时间消耗都由距离比较操作（DCOs）所占据。对于每个操作，它扫描一个对象的全部维度，因此在维度上运行的时间是线性的。

解决方法：提出了一种随机算法，名为ADSampling，它在大多数距离比较操作（DCOs）中运行时间是对数级别，并且具有高概率成功。（1. 缩短比较时间；2. 成功率高）

论文主要工作：

（1）提出一种随机算法ADSampling;

（2）基于ADSampling，我们开发了两种算法特定的技术作为插件来增强现有的AKNN算法。

其中，两种特定技术为：HNSW++和IVF++。

HNSW++是基于HNSW算法的改进，通过使用更好的近似距离和更高效的候选生成策略来提高搜索速度。

IVF++是基于IVF算法的改进，通过重新组织数据布局和调整维度顺序来提高缓存友好性，从而减少内存访问开销，提高搜索速度。

传统方法：

FDScanning：计算对象的距离（从查询点），然后将计算的距离与阈值进行比较。（需要扫描对象的全部维度来执行操作）

PDScanning：增量扫描原始向量的维度，并在基于部分扫描的𝑑维度的距离（如下图公式）大于距离阈值𝑟时终止该过程。

ADSampling核心：

将对象投影到具有不同维度的空间中，并基于投影向量进行比较操作（DCOs）以提高效率。

原理：对于远离查询的负对象来说，将它们投影到维数更少的空间就足以进行可靠的比较操作（DCOs）; 而对于靠近查询的负对象，它们应该被投影到具有更多维数的空间中以进行可靠的比较操作（DCOs）。

实现步骤：

（1）通过随机正交变换对对象进行预处理。（注：这一步仅是随机地旋转对象而不扭曲它们的距离。）

（2）在查询阶段处理不同对象的比较操作（DCOs）时，它会对其转换后的向量进行不同维度的采样。

注：ADSampling根据查询期间对象的DCO自适应地决定每个对象要采样的维度数量，而不是在索引阶段预设一个确定的数量（这需要具有专业知识，实践中难以设置）

ADSampling实现流程

随机向量投影过程

给定一个对象 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越大意味着假设检验的显著性值越小，这进一步意味着假设检验的结果越准确)。

图10绘制了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终止时，如果𝑑𝑖𝑠 ≤ 𝑟成立，则会发生失败，因为在这种情况下，它得出了𝑑𝑖𝑠 > 𝑟（通过拒绝零假设）。

ANN+

ANN+：在运行 AKNN 算法的过程中，每当它进行距离比较操作（DCOs）时，我们使用 ADSampling 方法。

HNSW+：在将新访问的对象的距离与结果集 R 中的最大值进行比较时使用 ADSampling 方法。

IVF+：将候选对象的距离与当前维护的 KNN 集合 K 中的最大值进行比较，以选择生成的候选对象中的最终 KNN 时应用 ADSampling。

ANN++

HNSW++

HNSW+：

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

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

R集的两个作用：

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

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

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

HNSW++：

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

集合R的分解：

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

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

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

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

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

IVF++

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

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

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

性能分析（6个数据集）

召回率：成功检索到的真实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的计算更重(如图2所示)

结论 3：

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

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

结论 4：

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

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

补充

索引阶段：

我们首先用NumPy库生成一个随机正交变换矩阵，存储它并将变换应用到所有数据向量。然后我们将转换后的向量(AKNN, AKNN*和AKNN**的原始向量)输入到现有的AKNN算法中。

对于HNSW、HNSW+、HNSW++和HNSW*(注意它们具有相同的图结构)，我们的实现基于hnswlib

对于IVF、IVF+、IVF++、IVF*和IVF**(注意它们具有相同的聚类结构)，我们的K-means聚类实现基于Faiss库

查询阶段：

所有算法都是用c++实现的

对于一个新的查询，我们首先使用特征库[25]转换查询向量，以便在运行AKNN+和AKNN++算法时进行快速矩阵乘法(对于AKNN, AKNN*和AKNN**，它们不涉及转换)。

然后我们将向量输入AKNN, AKNN+， AKNN++， AKNN*和AKNN**算法。

时间成分分析：

应用ADSampling需要随机转换数据和查询向量的额外成本。具体来说，转换数据向量的成本位于索引阶段，并且可以由同一数据库上的所有后续查询摊销。查询向量的转换在查询阶段进行，当出现查询时，查询的代价可以由回答相同查询所涉及的所有dco分摊。为了简单起见，我们将这一步(又称为Johnson-Lindenstrauss变换)实现为矩阵乘法运算，它需要𝑂(𝐷^2)时间。我们注意到，使用高级算法[19]可以在更短的时间内执行这一步，例如，使用Kac 's Walk需要𝑂(𝐷log𝐷)时间。

参考文献：

Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824-836. https://doi.org/10.1109/TPAMI.2018.2889473

Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128.