iQAN：在多核架构上利用高效查询内并行性实现快速准确的矢量搜索

3130iQAN：在多核架构上具有高效查询内并行性的快速准确向量搜索0ZhenPeng威廉姆斯学院威廉斯堡，美国弗吉尼亚州zpeng01@wm.edu0MinjiaZhang微软AI和研究贝尔维尤，美国华盛顿州minjiaz@microsoft.com0KaiLi肯特州立大学肯特，美国俄亥俄州kli17@kent.edu0RuomingJin肯特州立大学肯特，美国俄亥俄州rjin1@kent.edu0BinRen威廉姆斯学院威廉斯堡，美国弗吉尼亚州bren@cs.wm.edu0摘要由于其在新型人工智能应用中的应用，向量搜索在研究界引起了迅速增长的兴趣。最大化其性能对许多任务至关重要，但仍然尚未完全理解。在这项工作中，我们研究了使用查询内并行性来加速多核架构上最先进的基于图的向量搜索系统的可扩展性瓶颈的根本原因。我们的深入分析揭示了来自系统和算法两个方面的几个可扩展性挑战。基于这些见解，我们提出了一种名为iQAN的并行搜索算法，该算法具有一系列优化，可以提高收敛性，避免冗余计算并减轻同步开销。我们在一系列真实数据集上的评估结果显示，iQAN在从百万到亿数据集范围内的数据集上实现了比最先进的顺序基线低达37.7倍和76.6倍的延迟。我们还展示了iQAN在图大小或准确性目标增加时具有出色的可扩展性，在20亿规模的数据集上比最先进的基线提高了多达16.0倍，并且具有多达64个核心。0CCS概念：•信息系统→最近邻搜索；搜索具有辅助数据库。0关键词：近似最近邻搜索，基于图的，向量搜索，查询内并行0PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大©2023版权由所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.357752701 引言最近，最近邻搜索（NNS）因其在基于神经嵌入模型的语义搜索系统（例如图像、文本和视频）中的核心作用而受到关注。在语义向量搜索中，将非结构化数据�通过神经网络编码为嵌入向量，嵌入向量在高维空间��中，其中�的取值范围通常从100到1000，�的取值范围从百万到十亿。搜索根据向量之间的距离度量找到给定查询的�个最近嵌入。基于语义的搜索实现了新的应用，并在许多实际应用中得到应用。例如，主要电商巨头（例如亚马逊[46]）构建了嵌入产品目录和搜索查询的语义搜索引擎，然后推荐嵌入的搜索查询最接近的产品；Youtube[12]将视频嵌入到用于视频推荐的向量中；Web规模的搜索引擎将文本（例如word2vec[43]，doc2vec[32]）和图像（例如VGG[54]）嵌入到文本/图像检索[11,56]中，等等。由于搜索通常在在线交互应用程序中对每个查询进行，因此提出了降低NNS的延迟的重大挑战。许多工作旨在通过设计各种近似最近邻搜索（ANNS）算法来在实现高精度的同时降低搜索延迟，包括基于哈希的方法[2, 3, 13,25]，基于量化的方法[21, 27, 66, 67]，基于树的方法[10, 53,64]和基于图的方法[19, 37,68]。其中，基于相似性图的算法已经成为一类在高维ANNS上非常有效的方法，优于其他方法在各种数据集上实现最佳的精度与延迟之间的平衡[4, 19,38]。这些基于图的方法还已经与许多大规模生产系统集成[11,19,38]，在这些系统中，为了快速搜索和高精度而进行的优化具有明显的实际影响，因为生产系统对延迟和高精度要求严格：延迟或不准确的响应直接损害用户满意度并影响收入[17]。0本作品采用知识共享署名国际4.0许可协议。3140PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，鹅毛大学Zhen Peng、Minjia Zhang、Kai Li、Ruoming Jin和Bin Ren0尽管基于图的方法取得了有希望的结果，但仍存在限制其在实际场景中使用的挑战。特别是，随着数据规模的增长，同时实现低延迟和高准确性变得越来越具有挑战性。目前的解决方案通常通过将查询分派到多个处理器或节点以同时进行处理来采用查询间并行性。从吞吐量的角度来看，这种方法是可扩展的，但无法帮助减少查询延迟，因为每个查询仍然需要执行相同数量的向量计算来找到最近邻。减少延迟的另一个自然想法是利用多核处理器上的查询内并行性。例如，可以并行化顺序搜索算法中的每个迭代步骤中的节点扩展，希望在每个步骤中的多个工作线程可以并行检查多个邻居的接近程度，同时执行与顺序算法相同的计算。令人惊讶的是，这种解决方案表现非常糟糕，甚至可能比调优良好的顺序算法表现更差。然而，到目前为止，很少有研究探讨为什么查询内并行搜索在多核架构上对基于图的ANNS的加速有困难。在本文中，我们利用查询内并行性进行基于图的ANNS，并提出以下问题：如何在多核架构上实现基于图的ANNS算法的低搜索延迟和高准确性？特别是，该算法应该比最先进的ANNS实现具有明显优势。我们首先介绍了几项研究，揭示了直接并行化现有顺序图遍历策略的可扩展性差的根本原因。基于我们的研究，我们提出了一种名为iQAN的并行图搜索算法，该算法在图大小或准确性目标增加时提供了低延迟和高准确性，并具有出色的可扩展性。iQAN引入了一种名为路径并行性的新的并行方案，可以显著减少迭代深度。这种优化避免了搜索过程中的长串行依赖关系，但它对搜索效率提出了挑战：它引入了大量的冗余计算，导致计算和内存带宽消耗。为了减少冗余计算，iQAN引入了一种分阶段扩展方案，在搜索时只在最有效的位置进行路径并行性。最后，频繁的全局同步对并行图搜索的可扩展性有限。为了减少同步开销，iQAN引入了一种冗余感知同步策略，允许多个工作线程同时进行搜索，同时避免冗余计算和大量的同步，而不会丢失准确性。总之，本文作出了以下贡献：•深入研究，揭示了多核架构上最先进的向量搜索算法的可扩展性差的根本原因（第4节）。0•引入查询内并行优化，即路径并行、分阶段扩展和冗余感知同步，以加速搜索（第5节）。0•评估 iQAN并展示与现有解决方案相比的数量级延迟改进（第6节）。我们在Linux上用C++实现了iQAN，我们在各种数据集上的评估结果表明，对于从百万到亿级数据点，从�100维到�1000维嵌入向量，在不同的多核架构上，iQAN的延迟比现有解决方案（NSG[19]，HNSW[38]）降低了多达37.7倍和76.6倍。我们还观察到，随着图的大小或准确性目标的增加，iQAN具有出色的可扩展性，使其能够在20亿规模的数据集上以多达16.0倍的速度优于现有解决方案，并使用多达64个核心。最后，我们提供了性能分解和深入分析，以研究其关键优化对性能的影响，并与替代方法进行比较。2背景和相关工作02.1 ANN搜索优化0最近邻搜索的文献非常丰富，因此在这里我们将重点放在最相关的工作上。关于构建有效的ANN索引以加速搜索过程的工作非常多。早期的工作侧重于基于空间划分的方法。例如，基于树的方法（例如KD树[53]和R*树[10]）将数据空间分割成许多与树结构的叶子对应的区域，并且仅搜索有限数量的有希望的区域。然而，随着维度的增加（例如>16），这些方法的复杂度变得不比暴力搜索更高效[33]。之前的工作还在基于局部敏感哈希的方法上花费了大量的努力[2,3,13,25]，这些方法将数据点映射到多个桶中，并且通过某个哈希函数使附近点的碰撞概率高于其他点的概率。这些方法具有坚实的理论基础。LSH及其变体通常用于具有数十万维稀疏向量的情况。实际上，在大规模数据集上，基于图的方法（如[4,19,38]）已经比LSH方法取得了更好的性能。最近，Malkov和Yashunin发现满足小世界特性的图在寻找最近邻方面具有出色的导航能力。他们引入了Hierarchical Navigable SmallWorld（HNSW）[38]，它通过在建立具有小世界特性的层次k-NN图时添加额外的长距离链接来构建。对于每个查询，它执行一次遍历，最终收敛到具有对数复杂度的最近邻。随后，Fu等人提出了NSG，它近似于Monotonic Relative NeighborGraph（MRNG）[19]，该图也涉及到增强连接性的长距离链接。HNSW和NSG都被证明在达到相同召回率时检查的数据点要少得多[4,6,16,19,28,34,64,66]。2.2并行图处理并行图算法。有许多工作旨在将通用搜索方案并行化处理图（例如BFS[52]，DFS [44]，随机游走 [58]，波束搜索 [41]和分桶[55,72]）。然而，许多这些算法在设计时没有考虑到每个顶点关联的向量以及在严格的延迟约束下实现高召回率的目标。相比之下，我们分析了ANN的搜索效率挑战，并提出了优化方法来处理它们，以便在现代多核架构上扩展基于向量的相似性搜索。在不同的算法中，与我们最相关的工作可能是 Δ -stepping[72]，它按顺序对节点进行扩展以避免冗余的扩展。我们已经将 Δ -stepping应用于向量搜索，并将在第5.5节中提供更详细的讨论，并在第6节中进行比较。并行图框架。在过去的十年中，已经开发了许多图引擎和框架。其中一些是共享内存的，专注于在计算节点内处理内存中的数据集[47,60]，例如Galois [45]，Ligra[52]，Polymer [71]，GraphGrind [57]，GraphIt [72]，Graptor[62]和GraphBLAS [5]。一些是分布式系统[49]，例如Pregel [36]，GraphLab[35]，PowerGraph [22]和Gluon [14]。一些工作侧重于带外设计（例如GraphChi[31]和X-Stream[50]），并处理具有磁盘支持的大型图形。许多图形框架也在GPU上[42,63]，例如CuSha [30]，Gunrock [65]，GraphReduce [51]，Graphie [23]，Multigraph[24]，GraphBLAST [69]和Ascetic[59]。这些图系统要么基于顶点为中心的模型[36,70]，要么基于其变体（例如，以边为中心[50]）。这些并行图框架中的许多是专为通用并行图分析而设计的，而不是基于向量的相似性搜索。在这些已经成熟的编译器和优化技术的框架中实现ANN搜索是可能的，但需要解决复杂的可移植性挑战。首先，基于向量的相似性搜索使用特殊的数据格式来表示索引（例如，分层图或混合KD树加图结构[39]），这些格式不受现有图形框架的支持。其次，基于向量的相似性搜索需要良好设计的并行性和同步机制（甚至针对异构内存[26,48]），而现有图形框架提供的一般优化（例如，delta-stepping）无法提供足够的性能优势。因此，将这些更改移植到现有框架中，超越搜索算法本身，需要对整个系统栈进行更改。3150iQAN PPoPP ’23, 2023年2月25日至3月1日，加拿大蒙特利尔03准备工作 相似性图。相似性图是一个有向图 � =(�,�)，其中每个顶点 � � ∈ �对应于一个数据点或实体，边表示两个数据点之间的相似度。相似性图用于最近邻搜索，其中给定查询点 �，需要找到与其最相似的 �个邻居。在相似性图中，边的方向没有特定的含义，因为相似性是对称的。在本文中，我们将 � �  称为 � 的邻居，� �  称为 �的前�个最近邻。相似性图可以通过不同的方法构建，包括基于树的方法、基于哈希的方法、基于图的方法等。在本研究中，我们建议使用Hierarchical Navigable SmallWorld（HNSW）[38]构建相似性图。0算法1: 最佳优先搜索（BFiS）0输入：图 �，起始点 �，查询点 �，队列容量 � 输出：�个最近邻居点 �0优先级队列  �  ← � /*根据距离排序*/02 索引 � ← 00计算  ����(�,�)04 将 � 添加到 �0当  �  有未检查的顶点时执行 /*停止条件*/06 � 选择 � 顶点中第一个未检查的顶点的索引0将  � �  标记为已检查08 对于 � � 的每个邻居顶点 �  in  �0如果 � 没有被访问过则010 将 � 标记为已访问0计算  ����(�,�)012 将 � 添加到 � /* � 未被检查 */0如果  �.size() > �  则  �.resize(�)014 返回 � 中的前 � 个顶点0在一个 �  维嵌入向量集合中的向量 � �由实体在问题域中生成（例如，推荐系统中的视频或图像），这些实体具有语义含义。如果 � �属于由相似性图构建算法（例如，NSG [19]）确定的 �  的 �相对最近邻集合，则将顶点 � �  和 �  �通过边连接起来。图中没有自环或重复边。Top-K搜索。相似性图中的搜索通过最佳优先搜索（BFiS）[19]执行，其目标是仅搜索图节点的一小部分，以便根据与查询的接近度（例如，欧氏距离）找到前K个最近邻。BFiS从图的选择点（例如中心点或随机点）开始，并根据每一步中与查询的最近邻越来越接近，贪婪地遍历图的边，直到收敛到一个局部最优解（即找到的前K个最近邻）。算法1显示了其基本思想。搜索算法使用图节点的优先级队列（大小为�）来表示搜索过程中应该访问的邻居。起初，所有节点都处于未检查状态。在图遍历过程中，算法首先从队列中选择最近的未检查节点 � �，称为活动节点（第6行），并进行节点扩展。节点扩展计算 ��的所有邻居与查询的成对距离（第8-12行）。节点扩展后，搜索将有希望的邻居作为新的未检查候选项插入优先级队列，以供将来扩展使用。优先级队列中的候选项根据其与查询的距离进行排序，因此随着添加新的候选项，较不具有希望的候选项将被弹出（第13行）。搜索根据与查询的接近度（例如，欧氏距离）迭代地扩展未检查节点。当优先级队列中至少有 �个候选项且其中没有未检查节点时，搜索收敛，表明它已达到局部最优解。1248 16 32 64051015201248 16 32 640204060803160PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0度量。实际上，找到确切的前�个最近邻居可能非常耗时。因此，搜索过程只检查相似性图中的一部分向量，从而导致准确性与延迟之间的权衡。准确性通常通过召回率来衡量，即检索到的前K个候选者（�′）中真正最近邻居（�）的比例，定义如下[18]：0������ （� ′0| � ′ | = | � 0� （1）0低准确结果会降低用户满意度，因此希望获得高召回率。另一方面，延迟衡量了寻找前�个最近邻居所花费的时间。低延迟对于实现在线交互应用的ANN搜索至关重要。考虑到这些基本情况，我们现在定义本文中要解决的确切问题:问题定义。考虑到相似性图和具有�个处理器的多核架构，我们的目标是设计一种并行搜索算法，以使达到给定召回目标的搜索延迟最小化。0图4基于图的ANN搜索中的4个挑战我们首先讨论一种直观的并行实现并分析其在多核CPU上的成本。分析后将指导设计部分的设计。边缘化并行（EP）。鉴于对向距离计算（算法1中的第8-12行）彼此没有依赖性，自然想法是将邻居扩展步骤并行化，将距离计算分布到多个线程上。我们将此方案称为边缘化并行。边缘化并行允许邻居扩展在并行运行，并且在每个邻居上执行与顺序算法相同的计算。边缘化并行的另一个好处是，无论使用多少线程，它都返回相同的结果。尽管边缘化并行在简单性方面具有优势，但由于经过精心调整的顺序基准线，边缘化并行通常会获得次优性能。图1显示了在DEEP100M数据集上达到召回目标0.999时，使用边缘化并行的多线程搜索性能差，即从1个线程到64个线程都没有加速效果。在多核架构上，基于图的搜索的可扩展性差的原因是什么？原因1：边缘化并行导致高同步开销。放大边缘化并行的一个主要挑战是需要执行大量节点扩展以在大图上实现高准确性，导致需要进行数百次甚至数千次扩展。由于每次扩展都需要至少一次全局同步，以根据其到队列点的距离维护所有候选者的顺序，此频繁的全局同步为搜索过程增加了显著的同步开销。图2显示了0随着线程数的增加，同步开销占总搜索时间的50%以上，成为整体搜索延迟的决定因素。原则上，可以通过采用并发优先级队列或无锁算法在插入过程中减少同步开销。然而，我们发现还有其他严重限制并行搜索速度的挑战，如下所述。0延迟（毫秒）0图1.在Deep100M上的EP延迟。0同步开销（%）0图2. EP增加了高同步开销。0原因2：边缘化并行导致计算强度低，使得搜索过程难以充分利用内存带宽。我们使用英特尔处理器计数器监视器[15]在各种数据集和图上测量内存带宽利用率。数据移动主要来自节点扩展期间的向量加载。表1显示，使用单个线程执行时，仅使用了不到峰值硬件内存带宽消耗的3.4％（约80GB/s）的部分，这表明使用多线程利用更多带宽应该可以提高性能。然而，使用32路边缘化并行时，内存带宽利用率仅略微增加到最高4.2％。一些执行（例如SIFT1M）甚至观察到带宽消耗下降，这意味着边缘化并行具有较低的计算强度，使得难以使用所有可用的原始带宽。边缘化并行计算强度低的原因在于两个方面：（1）与矩阵乘法不同，逐点欧几里德距离计算是一种计算强度低的运算符；（2）在一步中要扩展的邻居数量有限，因为相似性图自然具有较低的出度，以避免出度爆炸问题。0表1. 测量内存带宽（GB/s）。基准测试 SIFT1M GIST1M DEEP10M SIFT100MDEEP100M0单个线程2.1 2.7 1.6 1.2 0.80边缘化64 thds. 2.0 3.4 2.0 2.7 1.60原因3：边缘化并行仍需要许多迭代才能收敛，导致步骤之间存在长时间的顺序依赖性。在算法1中，搜索执行一系列顺序迭代（第5-13行），其中每个迭代执行一个节点扩展。要扩展的节点取决于由先前步骤更新的优先级队列。此外，迭代次数取决于召回目标和图的大小。例如，图3显示，随着召回目标的增加，以及在一个亿级数据集DEEP100M上找到前100个最近邻居的迭代次数随之增加，召回目标从0.9增加到0.999时，增加了34.6倍。图4显示，随着数据集大小的增加，达到召回目标0.999的迭代次数也增加了，从100万向量数据集增加到1亿向量数据集增加了7.3倍。这种长时间的顺序依赖性使得在高准确性下实现低延迟尤为具有挑战性。0.900.951.000100020003000400050001000200030004000500013467811592 10Top-M, M = 312334543122450501000501000501001500501003170iQAN PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0迭代深度0图3.迭代深度随召回率的变化。0迭代深度0图4.迭代深度随数据大小的变化。0A:270B:290E:220K:110C:260D:240F:210H:170G:190I:150J:120M:70N:50L:90O:20SGS P:10 D0(a) BFiS较长的迭代深度。0A:270B:290E:220K:110C:260D:240F:210H:170G:190I:150J:120M:70N:50L:90O:20P:10(b) PP较短的迭代深度。0图5. BFiS（11步）与路径并行性（5步）的比较。0迭代深度0BFiS路径并行性0(a)找到第�个最近邻居所需的迭代深度（x轴）0未检查的数量0顶点0BFiS路径并行性0(b) 搜索收敛所需的步骤数。0图6.路径并行性通过比BFiS更少的迭代步骤收敛到局部最优。为了找到前1、前50和前100个近邻，PP平均只需3.4、5.0和5.4个步骤，显著减少。从未检查节点的角度来看，图6b显示，PP收敛到局部最优（即完成检查所有未检查的顶点）所需的步骤比BFiS少得多。我们指出BFiS的扩展过程类似于经典DFS/BFS中的树扩展。BFiS自然地引入了一个扩展树：树节点��是图�中的起始顶点��，树节点��（对应于图顶点��）的子节点是��的未访问邻居。BFiS的扩展与DFS有许多相似之处，因为每次，它只会扩展一个叶子节点。我们的路径并行性受到DFS/BFS的并行扩展的启发。然而，与DFS不同，DFS扩展最深的节点，PP同时扩展树的��个叶子节点，这些叶子节点是当前扩展树中查询��的��个最近邻居。因此，PP可以将BFiS的总迭代深度减少��倍。对于��步，PP可以扩展��×��个图节点。我们还注意到，边并行性是PP的一种特殊情况，其中�� = 1且�� = 1，而两种并行化都是在BulkSynchronousParallel（BSP）模型下进行的[61]，尽管BFiS具有相当有限的并行性可供探索。我们还注意到，在路径并行性中，访问映射由所有工作线程共享，以指示顶点是否已被访问。由于多个线程可能同时访问共享的访问映射，因此需要使用锁定或无锁算法来确保顶点仅被访问一次。幸运的是，即使顶点被多次计算，ANNS算法仍然正确，因为局部候选项肯定会合并回全局优先级队列。因此，多个线程不需要独占地更新访问映射，而是需要松散同步的访问映射。0.901.000.04164256001002000.900.951.000.00510150501003180PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔，魏振，张敏佳，李凯，金若铭和任斌0距离计算0边并行性 路径并行性0图7.BFiS与EP和PP的聚合距离计算，其中� = 64。0距离计算0迭代深度0迭代深度 距离计算0图8.迭代深度随着�增加而增加的路径并行性中的距离计算。0可以减少通信开销。我们使用位向量实现它以实现快速访问。05.2 通过分阶段扩展减少冗余计算虽然显著减少了迭代深度，但这是否意味着搜索过程现在可以在多核架构上获得期望的加速？答案是否定的。路径并行性减少了迭代深度，但同时引入了相当数量的额外距离计算，特别是当并行工作线程数量很大时。这是因为路径并行性增加了线程扩展不可行节点的可能性，而在边并行性中可以避免这种情况：扩展宽度�中的一些活动顶点可能不会从未来的角度导致最终的最近邻居。图7显示，为了达到相同的召回率（0.9-0.999），路径并行性通常需要执行比BFiS多得多的距离计算（1.3-3.5倍）。此外，我们还观察到，尽管通过增加并发扩展宽度�，迭代深度继续减少，但距离计算的数量却相反地增加，如图8所示。大量的冗余计算对搜索效率产生不利影响，因为许多线程正在加载用于不必要计算的向量，浪费了内存带宽和计算资源。为了减轻这种情况，我们研究了路径并行性在不同搜索阶段的有效性：路径并行性在哪个阶段最大程度地减少了迭代深度？我们发现总体上，在开始阶段，由于所有候选项都远离查询，早期扩展的候选项很可能被后来访问的更近的候选项抛弃。换句话说，在从未来的角度考虑，较早阶段扩展和检查的候选项很可能变得不必要。随着搜索向具有近邻的区域前进，覆盖更多搜索路径的较大扩展宽度可以有效地防止搜索陷入局部最小值。基于这些观察结果，我们提出了一个分阶段扩展（SE）方案，在搜索过程中每�步逐渐增加扩展宽度�和工作线程的数量。在实践中，我们将�的起始值设置为1，最大值设置为可用的硬件线程数。然后，对于每�步（例如� =1），我们将�的值加倍，直到�达到其最大值。图9a显示了无路径并行性和有分阶段扩展的路径并行性的比较结果。0距离计算0(a)BFiS，无PP和有分阶段扩展的距离计算。0未检查的数量0顶点0(b)每个搜索步骤后未检查候选项的数量。0图9. 有无分阶段扩展的路径并行性对比。� =64。有分阶段扩展的路径并行性显著减少了冗余的距离计算数量，使得距离计算与BFiS相当。另一方面，分阶段扩展能够保留路径并行性的优势，即在获得较小的迭代深度方面，如图9b所示。这些结果表明，通过在搜索的最有效阶段（即后期）执行路径并行性，平行搜索过程可以以减少的迭代深度和非常少的冗余计算添加来有效地收敛。05.3通过冗余感知同步减少同步开销并行搜索中剩余的性能挑战是同步，因为我们仍然需要决定何时进行同步。然而，减少基于图的ANNS的同步开销并不是一件简单的事情。图10显示，当我们在搜索迭代之间跳过同步时（即增加两次同步之间的间隔），同步开销（作为总时间的比率）显著减少。然而，减少同步会增加距离计算，特别是当同步间隔变大时。这是因为随着同步间隔的增加，个体工作线程更有可能搜索其本地但不具有前景的区域，而不切换到其他工作线程发现的新的有前景区域。因此，不能无限延迟同步，并且希望通过进行一小部分但有用的同步来实现整体高搜索效率，而不会产生太多的冗余计算。找到这样的间隔是一项非常困难的任务，因为查询相对于其近邻的距离在不同阶段的时间一直在变化。而且很难为所有查询找到一个固定的同步间隔。为了减少同步开销，iQAN执行冗余感知同步（RAS），允许工作线程通过添加一小组全局同步来执行低冗余计算的搜索。通过更新位置来衡量冗余扩展。我们引入了一个指标——更新位置，用于捕捉扩展过程中的冗余。当一个工作线程扩展一个未检查的候选项时，它的未检查邻居将被插入到该工作线程的本地队列中，并且我们定义20406080 1020406080100050100 150 200 2500501001503190iQAN PPoPP '23, 2023年2月25日至3月1日，加拿大蒙特利尔06.5×10 807.0×10 807.5×10 808.0×10 80同步开销（％）0距离计算0距离计算同步开销0图10.随着同步间隔的增加，同步开销和距离计算的变化。0平均更新位置0本地队列容量0图11.查询在搜索过程中的平均更新位置。0将更新位置定义为所有新插入候选项中最低（最好）的位置。因此，平均更新位置（AUP）是所有工作线程的更新位置的平均值。图11展示了在不进行任何全局同步的情况下，示例查询的AUP在搜索过程中如何变化。我们观察到，AUP逐渐增加，直到等于本地队列容量，并保持不变直到结束。当AUP接近队列容量时，表示大多数工作线程正在搜索无法找到有前景候选项来更新其本地结果的区域。因此，高AUP表示大多数工作线程正在进行冗余计算，并且通过进行全局同步可以使所有工作线程专注于搜索更有前景的区域，这些区域具有更高的包含更接近的近邻的概率。由于篇幅限制，iQAN的详细算法在补充材料中描述。它描述了如何使用AUP作为决定何时执行延迟同步的指标。给定队列容量�和位置比率� (0 < � ≤1.0)，执行同步的AUP阈值设置为� ∙�。如果检查器发现AUP等于或大于阈值，则触发全局同步。经验上，我们发现将比率�设置为0.9或0.8在大多数情况下效果良好。05.4成本分析0在这部分中，我们检查在多核处理器上执行的iQAN的成本。使用BFiS进行搜索的运行时间为：� ��� =  � ��� ×  � ��� (2)，其中� ���表示收敛到近邻的迭代次数，����表示一步内的节点扩展成本。现在考虑使用边级并行性的搜索，使用�个核心。这将导致执行时间：� �� =  � �� × ( � ��0� +  � ���� )(3)由于边级并行性只在�个工作线程之间分割节点扩展中的距离计算，并且在每一步之后仍然进行全局同步，因此� �� =  � ��=  � ���。边级并行性的可扩展性受到限制，因为迭代深度���较大，同步开销�����仍然很高。为了减少迭代深度，iQAN引入了路径级并行性，将� ��减少到� ��，其中� �� << � ��。0� �� =  � �� (↓↓) ×0� +  � ���� ) (4)0然而，这样做会增加节点扩展成本，从� ��增加到� ��，其中� �� >> ���，因为路径级并行性引入了冗余计算。为了避免冗余计算和同步开销，iQAN进一步引入了分阶段扩展和冗余感知同步，将节点扩展成本从� ��减少到� ��，对迭代深度���的影响最小，同时将平摊同步开销从� ����减少到����，从而实现搜索成本：0� iQAN  =  � ��  (↓↓0� +  � ���  (↓)) (5)05.5讨论：为什么不使用Δ-stepping？0一些并行图处理框架，如Galios [45]和GraphIt[72]，支持各种并行处理算法。因此，细心的读者可能会想为什么不将现有的并行图处理算法，如Δ-stepping[55]，应用于向量搜索问题。为了回答这个问题，我们将Δ-stepping应用于基于图的ANNS，并对其进行了一些修改以使其适应向量搜索。首先，我们保持优先队列的固定长度，而不是不断增加桶的数量，这会导致无限的搜索延迟，并且如果一个顶点的距离大于队列中的最后一个顶点的距离，则将其丢弃。这种改变允许我们通过调整队列长度来控制搜索预算，并避免扩展那些对于优化前K没有前景的候选项。其次，我们选择优先队列中的前�个未检查节点作为桶。我们不使用距离范围，因为由于维度灾难现象，成对向量之间的距离范围是非常动态的。第三，我们发现使用单个桶大小会严重影响性能，原因与第5.2节中描述的类似。因此，我们动态增加桶的大小。最后，我们让Δ-stepping在连续两次迭代中优先队列中的候选项保持不变，与iQAN一样停止。我们在第6.4节中提供了与Δ-stepping06.1评估方法基准。我们将iQAN与两种最先进的基于图的ANNS（NSG [19, 20]和HNSW [38,40]）进行比较。NSG使用BFiS，HNSW使用类似但稍作修改的实现来适应其分层索引。建立索引时使用的超参数根据其代码库或论文中提供的建议值进行设置。否则，测试了几个值，并报告了最佳性能。指标。我们使用延迟和召回率来衡量性能，如第3节所述。我们测量Recall@100（R@100），它衡量找到每个查询的前100个最近邻居的准确性，根据公式1，� =100。数据集。此评估使用五个数据集，这是在评估NSG和HNSW时的标准基准。SIFT1M0.900.951.000.51240.900.951.000.1250.520.900.951.001416642560.900.951.000.528321280.900.951.000.528320.900.951.000.25140.900.951.0014160.900.951.000.528320.900.951.001416640.900.951.000.528323200PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏志鹏，张敏佳，李凯，金若铭，任斌08 SIFT1M0iQANNSGHNSW0SIFT1M0iQANNSGHNSW01024 GIST1M0iQANNSGHNSW0GIST1M0iQANNSGHNSW0DEEP10M0iQANNSGHNSW016 DEEP10M0iQANNSGHNSW064 SIFT100M0iQANNSGHNSW0SIFT100M0iQANNSGHNSW0256 DEEP100M0iQANNSGHNSW0DEEP100M0iQANNSGHNSW0召回@1000延迟（毫秒）0图12.在KNL（32T）和Skylake（16T）上，HNSW、NSG和iQAN的延迟对比。06.2延迟加速的评估。图12比较了KNL和Skylake上HNSW、NSG和iQAN的延迟。NSG和HNSW使用它们的顺序搜索算法，而iQAN使用32个线程和0在KNL和Skylake上，分别使用16个线程。我们得出以下观察结果。首先，在所有五个数据集中，iQAN相对于现有的基于顺序的方法NSG和HNSW始终提供延迟加速，适用于广泛范围的召回目标。特别是，当召回目标从0.90增加到0.999时，iQAN的加速效果进一步增强。在KNL上，对于R@100的目标0.9、0.99和0.999，iQAN相对于NSG平均获得2.2倍、5.9倍和16.7倍的加速效果，在五个数据集上分别相对于HNSW获得2.8倍、8.1倍和27.6倍的加速效果。iQAN在大型图上获得了更多的延迟加速。值得注意的是，在KNL和Skylake上，iQAN相对于DEEP100M的NSG分别获得了37.7倍和12.9倍的加速效果，通过利用聚合的多核计算和内存带宽资源，在召回目标0.999时实现了低延迟（<5ms或<3ms），即使在极其交互式的在线应用中也可以实现对大规模图的高精度向量搜索。iQAN主要通过三个原因实现了显著的延迟加速。首先，iQAN的路径并行性有效地减少了迭代深度，使得顺序依赖关系不再是主要的瓶颈。这对于大型图（如DEEP100M）和高召回率（如0.999）尤为关键，因为在增加图的大小或增加召回目标时，迭代深度显著增加，正如第4节所示。其次，减少的迭代深度不会带来过多的冗余计算，因为iQAN通过分阶段扩展有效避免了路径并行性的冗余计算。第三，iQAN通过冗余感知同步显著降低了同步开销。其次，结果还表明，iQAN在不同的多核架构下也能实现延迟加速。在Skylake上，对于R@100的目标0.9、0.99和0.999，iQAN相对于NSG平均获得1.8倍、3.6倍和7.3倍的加速效果，在五个数据集上分别相对于HNSW获得2.1倍、5.6倍和14.0倍的加速效果。这些结果表明，iQAN的优化在不同的多核架构上具有良好的可移植性。0.900.951.000.1250.5280.900.951.000.528321280.900.951.000.52832128512408010020030012481632641248161248163264124812481632641248163210iQAN PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏志鹏，张敏佳，李凯，金若铭，任斌0图13. DiskANN和iQAN在KNL上的Recall@1延迟。0平均90.0% 95.0% 99.0% 02 40120 SIFT100M0NSG iQAN0平均90.0% 95.0% 99.0% 02 40DEEP100M0NSG iQAN0延迟（毫秒）0图14.iQAN和NSG在KNL上的百分位数延迟。其次，值得一提的是，随着嵌入向量的维度增加，iQAN在延迟加速方面的效果也越好。iQAN在KNL和Skylake上对GIST1M的加速效果超过HNSW76.6倍和24.9倍，这比我们在一个规模相似但维度要小得多的数据集（例如SIFT1M）上获得的加速效果更高。iQAN能够在更高维度的向量上实现更好的加速效果，因为随着向量的维度增加，成对距离计算的计算工作量也增加，这使得iQAN能够更多地从并行计算中获益。此外，图13还比较了DiskANN[26]（使用1个线程和其内存索引）和iQAN（使用32个线程）在KNL上的Recall@1目标的延迟。对于构建其SIFT1M和GIST1M数据集的索引，DiskANN使用了�=125、�=70、�=2，这与其论文中显示的设置相同。对于DEEP10M，DiskANN使用了�=100、�=100、�=1.2。图13显示，iQAN在延迟上也实现了比DiskANN更好的加速效果，尤其是对于高召回率的情况。例如，对于召回目标0.999，在这三个数据集中，iQAN相对于DiskANN的平均加速效果约为180.5倍。对于SIFT100M和DEEP100M，DiskANN需要的内存比KNL具有的搜索内存更大，这导致出现分段错误。减少尾延迟。对于在线推断来说，尾延迟和平均延迟一样重要，甚至更重要。为了查看iQAN是否提供稳定的加速效果，我们收集了SIFT100M和DEEP100M在召回目标为0.999时，KNL上NSG和iQAN的第90百分位数（90%tile）、第95百分位数（95%tile）和第99百分位数（99%tile）的延迟，结果显示，与平均值相比，NSG的99%tile分别增加了154%和91%，而iQAN的99%tile仅增加了31%和19%。iQAN导致尾延迟的增加相对较小，这可能是因为对于长查询，内部查询并行搜索特别有效，减少了延迟。06.3可扩展性评估0在这部分中，我们评估了iQAN在线程数量和图规模方面