313→××iQAN：在多核架构上快速准确的向量搜索和高效的查询内检索镇彭美国弗吉尼亚州威廉斯堡威廉玛丽学院zpeng01@wm.eduMinjia Zhang微软人工智能与研究中心美国华盛顿州贝尔维尤minjiaz@microsoft.com凯丽美国俄亥俄kli17@kent.edu肯特州立大学摘要金若明美国俄亥俄rjin1@kent.edu肯特州立大学任斌美国弗吉尼亚州威廉斯堡威廉玛丽学院bren@cs.wm.edu1引言向量搜索由于其在新的AI应用中的应用，引起了研究界的兴趣。最大化其性能对于许多任务至关重要，但仍然是初步理解。在这项工作中，我们调查的可扩展性瓶颈的根本原因，使用内部查询并行加速的国家的最先进的基于图形的向量搜索系统的多核架构。我们的深入分析揭示了几个可扩展性的挑战，从系统和算法的角度来看。基于这些见解，我们提出了iQAN，这是一种并行搜索算法，具有一组优化，可以提高收敛性，避免冗余计算，并减轻同步开销。 我们在广泛的真实世界数据集上的评估结果显示，iQAN达到了37。7和76。6比最先进的顺序基线更低的延迟，数据集范围从100万到1亿。我们还表明，随着图形大小或准确性目标的增加，iQAN实现了出色的可扩展性，使其在20亿规模的数据集上的性能超过最先进的基线高达16。0×，最多64个内核。CCS概念：·信息系统最近邻搜索;用辅助数据库搜索。关键词：近似最近邻搜索，基于图，向量搜索，查询内并行本作品采用知识共享署名国际4.0许可协议进行许可PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577527最近邻搜索（NNS）最近受到欢迎，这是由于其在使用神经嵌入模型为非结构化数据（例如图像、文本和视频）构建基于语义的搜索系统中的核心作用。 在基于语义的向量搜索中， 非结构化数据通过高维空间R中的神经网络编码为嵌入向量 ，其中 通常从100到1000， 从数百万到数十亿不等。搜索 基于向量之间的距离度量为给定查询找到最近的嵌入。基于语义的搜索使新的应用程序，并已被采用在许多现实世界的应用程序。例如，主要的电子商务参与者（例如，Amazon [46]）构建嵌入产品目录和搜索查询两者的语义搜索引擎，然后推荐其嵌入最接近嵌入的搜索查询的产品; Youtube [12]将视频嵌入到矢量中以用于视频推荐 ; Web规模 的 搜 索引 擎嵌 入文 本（ 例 如， word2vec[43]，doc2vec [32]）和图像（例如， VGG [54]）用于文本/图像检索[11，56]，等等。由于搜索经常发生在每个查询的在线交互式应用程序上，因此减少NNS的延迟已经提出了重大挑战。许多努力旨在通过设计各种近似最近邻搜索（ANNS）算法来减少搜索延迟，同时实现高准确度，包括基于散列的方法[2，3，13，25]、基于量化的方法[21，27，66，67]、树搜索算法[2，3，13，25]、基于量化的方法[2，27，66，67]、基于量化的方法[2，27，66，67]、基于量化的方法[2，27，66，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，67，基于方法[10，53，64]和基于图形的方法[19，37，68]。其中，基于相似性图的算法已经成为高维ANNS的一类非常有效的方法，在广泛的数据集上优于其他方法，以实现最佳的准确性与延迟[4，19，38]。 这些基于图形的方法也已与许多大规模生产系统集成[11，19，38]，其中快速搜索和高准确性的优化具有明确的实际影响，因为生产系统具有严格的延迟和高准确性要求：延迟或不准确的响应直接损害用户满意度并影响收入[17]。PPoPPZhen Peng，Minjia Zhang，Kai Li，Ruoming Jin，andBin Ren314···×××∼∼尽管基于图的方法有很好的结果，但仍然存在限制其在现实世界场景中使用的挑战。特别是，随着数据大小的增长，同时实现低延迟和高准确性变得越来越具有挑战性。当前的解决方案通常通过跨多个处理器或节点分派查询以同时处理来诉诸于查询间并行性[9，19]。这种方法从吞吐量的角度来看是可扩展的，但无助于减少查询延迟，因为每个查询仍然需要执行相同数量的向量计算来找到最近的邻居。减少延迟的另一个自然想法是利用多核处理器在单个节点上的查询内并行性。例如，可以在顺序搜索算法的每个迭代步骤中并行化节点扩展，希望多个工作线程可以并行检查多个邻居的接近度，同时在每个步骤上执行与顺序算法相同的计算。令人惊讶的是，这种解决方案的性能相当差，甚至可能比调优的序列算法差得多。然而，到目前为止，很少有研究探讨了为什么查询内并行搜索在多核架构上难以实现基于图的人工神经网络的加速。在本文中，我们利用查询内并行基于图的人工神经网络，并提出问题：如何实现低搜索延迟和高精度的基于图的人工神经网络算法在多核架构？特别是，该算法应该有一个明显的优势，国家的最先进的ANNS实现。 我们首先提出了几个研究，揭示了直接并行化现有的顺序图遍历策略的可扩展性差的根本原因。 基于我们的研究，我们提出了iQAN，一种并行图搜索算法，它同时提供低延迟和高准确性，同时随着图大小或准确性目标的增加而具有良好的可扩展性。iQAN引入了一种称为路径并行的新并行方案，该方案允许显著降低迭代深度。这种优化避免了搜索过程中的长顺序依赖关系，但它对搜索效率提出了挑战：它引入了大量的冗余计算，导致浪费的计算和内存带宽消耗。 为了减少冗余计算，iQAN引入了一种分级扩展方案，该方案仅在搜索时最有效的位置执行路径并行。最后，并行图搜索的可扩展性受到贪婪路由所需的频繁全局同步的限制。为了减少同步开销，iQAN引入了冗余感知同步策略，该策略允许多个工作线程并发执行搜索，同时避免冗余计算和大量同步，而不会损失准确性。总之，本文的贡献如下：进行深入的研究，揭示了国家的最先进的矢量搜索算法的可扩展性差的根本原因，多核架构上的算法（第4节）。引入查询内并行优化，即，路径并行、分级扩展和冗余感知同步，以加速搜索（第5节）。评估iQAN并显示与最先进的解决方案相比延迟改善的数量级（第6节）。我们在Linux上用C++实现了iQAN。我们对各种数据集的评估结果表明，iQAN达到了延迟比最先进的解决方案（NSG [19]，HNSW [38]）低37.7和76.6，适用于各种精度目标和数据集，范围从一百万到一亿个数据点，从100维到1000维嵌入向量，在不同的多核架构上。 我们还观察到，随着图形大小或准确性目标的增加，iQAN实现了出色的可扩展性，使其在20亿规模数据集上的性能优于最先进的解决方案，最高可达16.0，最多可达64个核心。最后，我们提出了一个性能分解和彻底的分析，以研究其关键优化的性能影响，并与其他方法进行比较。2背景和相关工作2.1ANN搜索优化最近邻搜索的文献是巨大的，因此，我们把我们的注意力集中在最相关的作品在这里。在构建有效的人工神经网络指标以加速搜索过程方面，已经做了大量的工作 早期的工作集中在基于空间划分的方法。例如，基于树的方法（例如，KD树[53]和R* 树[10]）分层地将数据空间划分为与树结构的叶子相对应的许多区域，并且只搜索有限数量的有希望的区域。然而，随着维度变大，这些方法的复杂性变得不比蛮力搜索更有效>16）[33].先前的工作还在基于局部敏感散列的方法上花费了大量的努力[2，3，13，25]，这些方法将数据点映射到具有特定散列函数的多个桶中，使得附近点的冲突概率高于其他点的概率。这些方法具有坚实的理论基础。LSH及其变体通常是为具有数十万维的大型稀疏向量而设计的在实践中，基于LSH的方法在大规模数据集上的表现优于其他方法，例如基于图的方法[4，19，38]。最近，Malkov和Yashunin发现，满足小世界特性，在寻找最近邻时表现出优异的可导航性他们引入了分层可导航小世界（HNSW）[38]，它构建了一个分层k-NN图，其中包含额外的长距离链接，有助于创建小世界属性。对于每个查询，它都会执行一次遍历，最终以对数复杂度收敛到最近的邻居随后，Fu et al. 提出了NSG，它近似于单调相对邻居图（MRNG）[19]，也涉及用于增强连接性的长距离链接。HNSWiQANPPoPP315←←（）下一页←∅（）下一页--≥和NSG已被证明通过检查少得多的数据点来实现相同的召回率，从而优于现有方法[4，6，16，19，28，34，64，66]。2.2并行图形处理并行图算法。有许多努力旨在使图上的通用搜索方案并行化（例如，BFS [52]，DFS [44]，随机游走[58]，波束搜索[41]和桶[55，72]）。然而，这些算法中的许多被设计为没有考虑具有与每个顶点相关联的向量以及在严格的延迟约束下实现高召回率的目标。相比之下，我们分析了ANN的搜索效率挑战，并提出了优化来处理它们，以允许基于向量的相似性搜索在现代多核架构上扩展 在不同的算法中，与我们最相关的工作是per-silo Δ-stepping[72]，它分阶段扩展节点以避免冗余扩展。我们应用算法1：最佳优先搜索（BFiS）输入：图形输入、起点输入、查询输入、队列容量输入输出：的最近邻1优先级队列*/*根据距离排序*/2指数 03计算器，计算器4.将“”添加到“”5whilevectorhas unchecked verticesdo/*stop condition*/6中 第一个未检查折点的索引7标记为已检查8foreachneighborcropsofcropsincrops9如果没有访问，则参观了10个马克·库哈斯11计算器，计算器12将添加到/*未选中*/13if. size（）>sizethen.resize（）14返回第一个顶点的顶点Δ-步进到矢量搜索，并将提供更详细的第5.5节中的讨论和第6节中的比较。在一组10 维嵌入向量中的向量并行图框架。在过去的十年中，已经开发了许多图形引擎和框架。其中一些是共享内存，专注于处理计算节点内的内部数据集[47，60]，例如，[52]第一次世界大战后，中国的经济和社会发展受到了很大的影响。[72]，Graptor [62]，GraphBLAS [5]。有些分布在系统[49]，例如， [36][37][38][39][3 一些努力集中于核外设计（例如，GraphChi [31]和X-Stream [50]），并使用磁盘支持处理大型图形。 许多图形框架也在GPU上[42，63]，例如CuSha [30]，Gunrock [65]，[51]、Graphie [23]、Multigraph [24]、Graph-BLAST [69]和Ascetic [59]。这些图系统基于顶点中心模型[36，70]或其变体（例如，边缘中心[50]）。这些并行图框架中的许多主要是为通用并行图分析而设计的，在这些具有成熟编译器和优化技术的框架中启用ANN搜索是可能的，但需要解决重要的可移植性挑战。首先，基于矢量的相似性搜索使用特殊的数据格式用于索引（例如，分层图或混合KD树加图结构1 [39]），这不被现有的图框架支持。其次，基于向量的相似性搜索需要设计良好的并行性和同步机制（甚至针对异构存储器[26，48]），而现有图形框架提供的一般优化（例如，增量步进）不能提供足够的性能益处。因此，将这些变化移植到现有的框架，超出搜索算法本身，需要整个系统堆栈的变化。3预赛相似图 相似图是一个有向图���=（���������=1，...，. 在实践中，嵌入向量由问题域中的实体生成（例如，推荐系统中的视频或图像），其承载语义。如果顶点R1属于由相似性图构造算法（例如，NSG[19]）。图中没有自边或重复边Top-K 搜 索 相似性 图 中的搜索是 通 过 最佳 优 先 搜 索（BFiS）[19]执行的，其目的是仅搜索图节点的一个小子集，以基于它们的接近度找到前K个最近邻居（例如，Euclidean distance）到查询。BFiS开始于选定的（例如，中点或随机）点并且通过在每一步更接近最近的邻居来遍历图的边缘直到它收敛到局部最优（即， 找到前K近邻）。算法1给出了它的基本思想。 搜索算法维护一个大小���为图节点（ ���）的优先级队列，指示搜索过程应该访问哪些邻居。一开始，所有节点都处于未选中状态。 在图遍历过程中，算法首先从队列中选择最近的未检查节点������，称为活动节点（第6行），并执行节点扩展。 节点扩展计算查询的所有邻居的成对距离������（第8 - 12行）。 在节点扩展之后，搜索将有希望的邻居插入到优先级队列中，作为未来扩展的新的未检查的候选者。优先级队列中的候选项根据它们与查询的距离进行排序，因此当添加新的候选项时，不太有希望的候选项将被弹出（第13行）。搜索基于未检查的节点的接近度（例如， Euclidean distance）到查询。当优先级队列中至少有100个候选节点并且没有未检查的节点时，搜索收敛，这表明它已经达到局部最优。PPoPPZhen Peng，Minjia Zhang，Kai Li，Ruoming Jin，andBin Ren316延迟（ms）Sync.间接费用∼公制。在实践中，找到确切的前向搜索可能非常耗时。结果，搜索过程仅检查相似性图中的向量的子集，从而导致准确性对延迟的权衡。准确率通常由召回率来衡量，召回率是检索到的前K个候选者（ K′）中的真实最近邻（K ′）的分数，定义如下[18]：随着线程数量的增加，同步开销占总搜索时间的50%以上，成为整个搜索延迟的主要因素原则上，可以通过在插入期间采用并发优先级队列或无锁算法来减轻这种同步开销。然而，我们发现，还有其他挑战严重限制了平行������������������ （���′）=|���′∩���|为|���′∩���|（一）搜索速度，如下所述。|���2080|���2080高召回率是期望的，因为低准确度的结果降低了用户满意度。 另一方面，延迟度量的是寻找最接近的 邻居所花费的时间. 低延迟是至关重要的，特别是使人工神经网络搜索在线交互式应用程序.在给定的前提下，我们现在定义我们在本文中处理的确切问题：151050124816 32 64的线程图1. EP在Deep100M上的延迟。6040200124816 32 64的线程图2. EP增加了高同步。头顶问题定义。 考虑到相似性图和多核架构与 处理器，我们的目标是设计一个并行搜索算法，使搜索延迟达到一个给定的召回目标是最小化。4基于图的ANN搜索中的挑战我们首先讨论一个简单的并行实现，并分析其在多核CPU上的成本分析稍后将在设计部分中指导设计边缘并行（Edge-wise parallelism，EP）。假设成对距离计算（算法1中的第8 - 12行）在迭代中彼此不相关，则通过将距离计算拆分到多个线程来并行化邻居扩展步骤是一个自然的想法。 我们将此方案表示为边并行。边缘并行允许邻居扩展并行运行，同时对每个邻居执行与顺序算法相同的计算。边并行的另一个好处是，无论使用多少个线程，每次执行都返回相同的结果尽管它在简单性方面有好处，但这种自然的想法并不能带来良好的加速。事实上，由于良好调优的顺序基线，边缘并行通常会达到次优性能。图图1显示，为了在DEEP 100M数据集上达到0.999的召回目标（详细设置可以在第6节中找到），具有边缘并行性的多线程搜索表现不佳，即， 从1到64个线程没有加速。是什么原因导致基于图的搜索在多核架构上的可扩展性差？原因1：边缘并行导致高同步成本。 扩展边并行性的一个主要挑战是需要执行大量的节点扩展以在大型图上实现高精度，从而导致数百甚至有时数千次扩展轮。 由于每一轮都需要至少一个全局同步，以根据所有候选者到队列点的距离来维持所有候选者的顺序，因此这种频繁的全局同步给搜索过程增加了显著的同步开销。图2显示原因2：边并行导致计算强度低，使得搜索过程难以充分利用内存带宽。我们使用英特尔处理器计数器监视器[15]来测量各种数据集和图形下的内存带宽利用率。 数据移动主要来自节点扩展时的加载向量。 表1显示，单线程执行仅使用英特尔至强融核处理器上峰值硬件内存带宽消耗（80GB/s）的3.4%以下，表明多线程利用更多带宽应能带来更高性能。然而，使用32路边缘并行，内存带宽利用率仅适度增加至4.2%。 一些例外情况（例如，SIFT 1M）甚至观察到带宽消耗降低，这意味着边缘并行具有低计算强度，这使得使用所有可用的原始带宽具有挑战性。边并行计算强度低的原因在于两个方面：（1）与矩阵乘法不同，逐点欧氏距离计算是一个计算强度低的运算符;（2）考虑到相似图自然具有低出度以避免出度爆炸问题，一步中要扩展的邻居数量有限[19]。表1.内存带宽（GB/s）测量。基准SIFT 1M GIST 1M 深10米SIFT 100M 深度100米单次THD边缘方向64度2.12.02.73.41.62.01.22.70.81.6原因3：边缘并行仍然需要许多迭代来收敛，导致步骤之间的长顺序依赖性。在算法1中，搜索执行一系列顺序迭代（第5 - 13行），其中每个迭代执行节点扩展。扩展哪个节点取决于前面步骤更新的优先级队列。此外，迭代次数取决于召回目标和图的大小。例如图图3显示，随着召回目标的增加，在一亿规模数据集DEEP 100 M上找到前100个最近邻居的迭代次数随着召回目标的增加而急剧增加。iQANPPoPP317×更高（例如， a 34。6倍从0.9增加到0.999召回）。图 4示出了随着数据集大小的增加，找到召回目标0.999的结果的迭代次数也增加（例如，7.第一次会议。从1M向量数据集到100M向量数据集的3倍 这种长时间的顺序依赖性使得实现高精度的低延迟尤其具有挑战性。500040003000500040003000（a）BFiS（b）PP20002000图5. BFiS（11个步骤）与路径并行（5步）。100000.90 0.951.00召回@10010000DEEP1M深10米深度100米数据集100100BFiS路径并行图3. 迭代深度随着召回而变化。5iQAN的设计图4. 迭代深度随数据大小而变化。5000 50100找到最近的邻居5000 50 100 150搜索步骤为了应对上述挑战，我们将iQAN，一种加速基于图(a) 迭代深度以找到第三个最近邻（x轴）。(b) 搜索收敛的步数。多核架构上的ANNS。5.1通过路径智能化减少迭代深度在每次搜索迭代中，BFiS执行节点扩展到最有希望的未经检查的候选者。在iQAN中，我们通过放松优先级顺序并让每个线程扩展更多节点（例如， 顶部 未检查的候选者）在每个步骤中作为用于扩展的活动节点。我们还放松了同步，使全球同步后，只有几个扩展步骤。我们称这种扩展节点的新方法为路径并行（PP）。算法中的这种小变化导致查询的迭代深度的显著减少，例如，从几千到几十为什么这个改变会减少迭代的深度？多节点扩展和宽松的同步相当于让每个线程在进行全局同步之前探索局部区域中的路径，而不是单个节点的邻居列表。通过这样做，它增加了在更少的迭代次数中找到最近邻居的可能性从概念上讲，这可以在图1中示出5a. 它显示BFiS的搜索路径在每个搜索步骤中仅扩展一个节点，标记为虚线箭头。在第一步之后，���是主动节点。但是，它不能导致更接近的候选者，因此它回溯到未检查的候选者。同样的回溯也发生在���to���和���to之间 。因此，BFiS有一个很长的搜索路径来找到所有最近的邻居。相比之下，Fig.5b示出了通过让线程扩展前3个有希望的候选（例如， = 3），在第一步之后，���并且���都是活动节点;因此，到最近邻居的搜索路径立即开始，而不像在BFiS中那样等待轮到它。因此，虽然BFiS的迭代深度为11，但路径并行度仅为5。我们进行了实验研究，以验证这一变化的有效性图图6示出了在数据集SIFT 1M上使用具有0的10K查询的BFiS和PP之间的迭代深度的比较结果。90个召回目标。我们设定64.第总体而言，虽然BFiS需要10.1，69.4和88.1步图6.路径并行收敛到局部最优的迭代步骤比BFiS小得多。为了找到前1、前50和前100个近邻，PP平均仅分别花费3.4、5.0和5.4步，这是显著的减少。 从未检查节点的角度来看，图。图6b示出了PP也需要少得多的步骤来收敛到局部最优（即， 完成检查所有未检查的顶点）而不是BFiS。我们注意到BFiS的扩展过程类似于经典DFS/BFS中的树扩展 BFiS自然地引入了一个扩展树：树的根节点是图中的起始顶点;树节点的子节点（对应于图顶点）是的未访问邻居。BFiS的扩展与DFS有许多相似之处，因为每次只扩展一个叶节点。我们的路径并行的启发并行扩展DFS/BFS。然而，与DFS只扩展最大深度的树不同，PP扩展 的是当前扩展树的所有叶子中查询的最近邻居。因此，PP可以潜在地将BFiS的迭代深度的总数 减少倍。 对于 步骤，PP可以扩展图节点。我们还注意到，边方向并行性成为PP的特殊情况，其中并且两种并行化都是在批量同步并行（BSP）模型[61]尽管BFiS具有相当有限的并行性可供探索。我们还注意到，在路径并行，visiting地图是由所有工人共享，以表明如果一个顶点已被访问。 由于多个线程可以同时访问共享的访问映射，因此需要锁定或无锁算法来确保顶点仅被访问一次。 幸运的是，ANNS算法仍然是正确的，即使一个顶点被计算多次，因为本地候选人被保证合并回全局优先级队列。因此，多个线程不需要专门更新访问映射和松散同步的扩展访问回溯1答：H：起始点最近邻查询点英210L：911F：213乙：K：11个4N：55P：19OC：G：约：男8D：24I：151答：2711乙：二H：1723英L：94P：基：113女：212人423O：2C：G：约：5男5D：24I：15BFiS路径并行迭代深度迭代深度迭代深度Num. 未检查的顶点PPoPPZhen Peng，Minjia Zhang，Kai Li，Ruoming Jin，andBin Ren3181.5×1081.0×1085.0×1070.02×1081×1080迭代深度距离比较20010001.5×1081.0×1085.0×1070.0100500PPPP + SE0.90 0.95 1.00召回@100图7. BFiS的聚合距离计算4 16 64 256W图8. Dist.计算如ITER一样增加。深度0.90 0.95 1.00召回@100(a) Dist. 计算BFiS、PP w/o和w/分级膨胀。0 5 10 15搜索步骤(b) 每个搜索步骤后未选中的候选日期数w/EP和PP，其中λ=64。PP折痕增加，图9. 路径并行性与可以减少通信开销。 我们使用位向量实现它以实现快速访问。5.2通过分级扩展减少冗余计算虽然大大减少了迭代深度，但这是否意味着搜索过程现在将在多核架构上获得所需的加速答案是否定的。 路径并行性降低了迭代深度，但同时引入了大量的额外距离计算，特别是当并行工作者的数量很大时。这是因为路径并行性增加了线程扩展在边并行性中本可以避免的无希望节点的可能性：扩展宽度N之外的一些活动顶点从未来的角度来看可能不会导致最终的最近邻居图图7示出了为了达到相同的召回率（0.9 - 0.999），路径并行通常需要执行比BFiS显著更多的距离计算（1.3-3.5倍）。此外，我们还观察到，虽然通过增加并发扩展宽度，，则距离计算的数量相反地增加，如图2所示。8 .第八条。大量的冗余计算会对搜索效率产生不利影响，因为许多线程正在加载用于不必要计算的向量，从而浪费内存带宽和计算资源。为了减轻它，我们调查的有用性路径并行在不同的搜索阶段：在哪个阶段的路径并行减少迭代深度最多？我们发现，总的来说，在开始时，由于所有的候选都远离查询，那些早期扩展的候选很可能被稍后访问的更接近的候选丢弃换句话说，在早期阶段扩展和检查的候选人很有可能从未来的角度变得不必要 随着搜索向前移动到具有最近邻居的区域，覆盖更多搜索路径的更大扩展宽度可以有效地防止搜索陷入局部最小值。根据这些观察，我们提出了一个阶段性的扩展-通过逐渐增加扩展宽度的方案在搜索过程中，每隔一段时间就有一次搜索和工作人员的数量。在实践中，我们将tcp的起始值设置为1，最大值设置为可用硬件线程的数量然后，对于每一步（例如， = 1）我们将的值加倍， 直到 达到最大值。图图9a示出了在没有和没有阶段性扩张。 =64。分阶段扩张。分阶段扩展显著减少了冗余距离计算的数量，导致距离计算与BFiS相当。 另一方面，分级扩展能够在获得减少的迭代深度方面保持路径并行的好处，如图所示。9b. 这些结果表明，通过在它们最有效的地方（即，搜索的后期阶段），所以并行搜索过程可以有效地收敛，同时减少迭代深度，并且在多个工作者之间增加非常少的冗余计算。5.3通过冗余感知同步减少同步开销并行搜索中剩下的性能挑战在于同步，因为我们仍然需要决定何时进行同步。然而，减少基于图的ANNS的同步开销是不平凡的。图10示出了当我们在搜索迭代之间跳过同步时（即， 增加两个同步之间的间隔），同步开销（显示为与总时间的比率）显著降低。然而，decreas- ing同步增加距离计算，尤其是当同步间隔变大。这是因为当我们增加同步间隔时，它增加了个体工作者搜索其本地但没有希望的区域而不切换到由其他工作者发现的新识别的有希望的区域因此，不能无限地延迟同步，并且期望小集合但有用的同步以实现整体高搜索效率而不引起太多冗余计算。发现这样的间隔原来是不平凡的，因为查询与其近邻的相对距离在不同阶段一直变化。也很难为所有查询找到一个固定的同步间隔。 为了减轻同步开销，iQAN执行冗余感知同步（RAS），其允许工作者通过添加全局同步的最小集合来执行具有低冗余计算的搜索。通过更新位置测量冗余扩展我们引入了一个度量-更新位置-来捕获扩展过程中的冗余。当一个工作线程扩展一个未检查的候选对象时，它的未检查的邻居被插入到工作线程路径并行性边缘并行性PPPP + SEBFiS距离补偿迭代深度距离补偿距离计算Num. 未检查的顶点iQANPPoPP319·≤×100Dist. 计算8.0×108150然而，这样做会增加节点扩展成本80同步间接费用607.5×108本地队列容量100来自到，其中，公司简介因为路径方面407.0×1082006.5×10820406080 100500050100 150 200 250并行性引入了冗余计算。为了避免再-冗余计算和同步开销进一步引入分阶段扩展和冗余感知同步间隔图10. Sync.开销和距离计算作为同步。间隔增加。搜索步骤图11. 查询同步，这将节点扩展成本从最小化减少到最小化，同时对迭代深度的影响最小同时减少分期同步开销从搜索引擎到搜索引擎，导致搜索更新位置作为所有新插入的候选的最低（最佳）位置平均更新位置（AUP）公司简介 =（↓↓）×（（↑）+���������（↓））（五）是所有工人更新位置的平均值图11演示了一个示例查询的AUP在搜索过程中如何变化，而不进行任何全局同步。我们观察到，AUP逐渐增加，等于本地队列容量，并保持平稳结束。 当AUP接近队列容量时，它表明大多数工作者正在搜索无法找到有希望的候选者以更新其本地结果的区域。因此，高AUP指示大多数工作者正在进行冗余计算，并且它将受益于全局同步，使得所有工作者可以专注于搜索更有希望的区域，这些区域具有更高的包括更近的近邻的概率。由于篇幅所限，iQAN的详细算法将在补充材料中描述它描述了如何使用AUP作为度量来决定何时执行延迟同步。 给定队列容量���和位置比���（0 <���1. 0），则进行同步的AUP的阈值设置为��� 。如果检查器发现AUP等于或大于阈值，则触发全局同步。根据经验，我们发现将比率���设置为0。9或0。8在大多数情况下都很好5.4成本分析在这一部分中，我们研究了iQAN在多核处理器上执行的成本。使用BFiS搜索的运行时间为：5.5讨论：为什么不使用Δ步进？一些并行图形处理框架，如Galios [45]和GraphIt [72]支持各种并行处理算法。因此，细心的读者可能会想，为什么不将现有的并行图处理算法（如Δ-stepping[55]）应用于向量搜索问题。为了回答这个问题，我们将Δ-stepping应用于基于图的ANNS，并进行了一些修改，使其适应向量搜索。首先，我们保持一个固定长度的优先级队列，如果一个顶点的距离比队列中最后一个顶点的距离大，我们就丢弃它，而不是不断增加桶的数量，这会导致无限的这一变化允许我们通过调整队列长度来控制搜索预算，并避免扩展没有希望用于细化top-K的候选。其次，我们选择优先级队列中第一���个未检查的节点作为存储桶。我们不使用距离范围，因为成对向量距离的范围由于维数灾难现象而非常动态第三，我们发现使用单个桶大小会显著损害性能，原因与第5.2节中描述的相似。因此，我们动态地增加存储桶大小。最后，当优先级队列中的候选者连续两次迭代保持相同时，我们让Δ步进停止，与iQAN相同。我们在6.4节中提供了与Δ步进的比较结果。6评价哪里=(2)表示要收敛6.1评价方法到近邻，并且表示一步内节点扩展的成本。 现在考虑使用核心的边并行搜索 。这将导致执行时间：基线。 我们将iQAN与两种最先进的基于图形的ANNSNSG [19，20]和HNSW [38，40]进行了比较。NSG使用BFiS，HNSW使用类似但略有修改的方法，fied实现适应其分层索引。的=（���公司简介（三）用于构建其索引的超参数基于来自其代码库或论文的建议值设置，如果由于边向并行性仅划分距离com，在每个步骤之后仍然进行全局同步的同时，在跨多个工作进程的，边并行的可扩展性是有限的，因为迭代的深度是大的，同步成本仍然很高。为了减少迭代深度，iQAN引入了路径并行性，其将迭代次数减少为迭代次数，其中迭代次数减少为迭代次数。 <<由作者提供否则，将测试多个值，并报告最佳性能。指标. 我们使用延迟和召回来测量性能，如第3节所述。我们测量Recall@100（R@100），它测量为每个查询找到前100个最近邻居的准确性，根据等式 1 = 100。数据集。本次评估使用了五个数据集，它们是标准的，=（↓↓）×（↑↑）+（↑））（4）在评估NSG和HNSW时，SIFT 1MDist. Compt.Sync. 间接费用Avg.更新位置PPoPPZhen Peng，Minjia Zhang，Kai Li，Ruoming Jin，andBin Ren320SIFT 1MNSGiQANGIST 1MNSGiQAN深10米NSGiQANSIFT 100MNSGiQAN深度100米NSGiQAN××××× ××× ××× × ××8 10244256642161464 2563216648162440.50.90 0.951.0010.90 0.95 1.00 0.90 0.951.0010.90 0.951.0010.90 0.95 1.00HNSW2NSGSIFT1M128HNSWGIST1M16深10米HNSWNSGSIFT 100M32HNSW深度100米32HNSWNSGiQAN0.532iQAN824iQAN18iQAN28个iQAN20.1250.90 0.95 1.000.5 0.90 0.95 1.000.25 0.90 0.95 1.000.5 0.90 0.95 1.000.50.90 0.95 1.00召回@100图12.图的第一行和第二行分别显示了KNL（32 T）和Skylake（16 T）上HNSW、NSG和iQAN之间的延迟比较。（128D）和GIST1M（960D）来自Jégou et al. [1，28];SIFT 100 M （ 128 D ） 从 Jégou 等 人 引 入 的 SIFT 1B（bigann）中随机采样。 [29]; DEEP 10 M（96 D）和DEEP 100 M（96 D）是Babenko和Lempitsky [7，8]发布的DEEP 1B的子集。在此基础上，我们还尝试对20亿尺度的数据集SIFT 1B（128D）和DEEP 1B（96D）进行了然而，在我们的测试平台上，它们很容易耗尽内存，内存为128GB（例如，DEEP1B将需要>384GB的内存来加载嵌入向量）。这可能也是为什么以前的工作没有评估这两个数据集。因此，我们在具有1.5TBDRAM的专用机器上运行了十亿级数据集。 我们在附录中提供了数据集的详细信息。实施. 我们的iQAN实施基于使用C++的最先进的NSG [19]。对于给定数据集（例如，1M我们使用NSG代码库建议的超参数来构造图，因为它们在实践中表现得很好最初的NSG论文没有评估十亿规模的数据集，因为它们占用了巨大的内存。对于十亿规模的数据集，我们使用具有足够大的DRAM来构建NSG图的机器然后，我们使用基准测试提供的查询向量进行最终评估。 我们将平均更新位置比率设置为0。SIFT1M、GIST1M 和 SIFT 100 M 为 8 ， 9 个 用 于 DEEP 10M 和 DEEP100M。平台和设置。 我们进行了我们的实验工作站与至强Phi7210（1.30 GHz）与64个核心和109 GB的DRAM（简称KNL）和工作站与至强黄金6138（2.00 GHz）与20个核心和128 GB的DRAM（简称天空湖）。为了进一步评估20亿规模的数据集，我们使用了一台配备Xeon Gold 6254（3.10 GHz）的机器，该机器具有72个内核和1.5 TB内存。6.2延迟加速的评估图图12比较了HNSW、NSG和iQAN在KNL和Skylake上的延迟NSG和HNSW使用其顺序搜索算法，而iQAN使用32个线程，16线程，分别在KNL和Skylake。我们提出以下意见。首先，在所有五个数据集中，iQAN始终提供在广泛的召回目标范围内，比现有的基于序列的方法NSG和HNSW提高了速度。特别地，来自iQAN的加速随着召 回 目 标 移 动 到 高 准 确 度 区 域 （ 例 如 ， 从 0.90 到0.999）。在KNL上，对于R@100目标0.9、0.99和0.999，iQAN实现二、二五9和16。在五个数据集上平均比NSG加速7倍，八八1和27。6在HNSW。 iQAN在大型图形上实现了更大的延迟加速。值得注意的是，iQAN达到了37。7和12。在KNL和Skylake上的DEEP 100M上比NSG加速了9倍，<<通过利用聚合的多核计算和内存带宽资源，在召回目标0.999时获得了5ms或3ms的低延迟。这使得向量搜索具有非常高的精度在大规模的图形，即使在非常互动的在线应用程序。iQAN实现了显著的延迟加速，主要有三个原因。首先，iQAN这对于大型图（例如，DEEP 100M）和高召回率（例如，0.999），如第4节所示，随着我们缩放图形大小或增加召回目标，迭代深度显著增加。其次，减少的迭代深度不会以许多冗余计算为代价，因为iQAN利用分阶段扩展来有效避免进行路径并行的冗余计算。第三，iQAN通过冗余感知同步显著降低了同步开销。其次，结果还表明，iQAN表现出延迟在不同的多核架构中实现加速在Sky-lake上，对于R@100目标0.9、0.99和0.999，iQAN也实现了1 .一、八三6和7。平均比NSG提高3倍，一、五、6和14。0比HNSW高。这些结果表明，iQAN中的优化在不同的多核架构之间具有良好的可移植性。延迟（ms）iQANPPoPP321艾安GIST 1M艾安深10米艾安R=0.995R= 0.99R=0.995R= 0.99R=0.995R= 0.99L1缺失×××× ××820.5SIFT1M1283282512128328232GIST1M1684216SIFT100M8
