GGNN: 基于图的 GPU 最近邻搜索

摘要

在高维空间中进行近似最近邻（ANN）搜索是多种计算机视觉系统的核心部分，并在具有显式内存表示的深度学习中变得越来越重要。自从 PQT（Wieschollek 等，2016）、FAISS（Johnson 等，2021）和 SONG（Zhao 等，2020）开始利用 GPU 所提供的大规模并行计算能力后，基于 GPU 的实现已成为当今最先进 ANN 方法的重要资源。虽然这些方法大多能加速查询，但对加速底层索引结构构建的关注相对较少。本文提出了一种基于最近邻图和图上信息传播的 GPU 友好搜索结构。我们的方法旨在利用 GPU 架构加速索引结构的分层构建以及查询执行。实证评估表明，GGNN 在构建时间、准确性和搜索速度方面显著优于最先进的基于 CPU 和 GPU 的系统。

作者

Fabian Groh Amazon 图宾根, 图宾根, 德国 ORCID: 0000-0001-8717-7535

Lukas Ruppert 计算机图形组，图宾根大学，图宾根，德国 ORCID: 0000-0002-0249-7706

Patrick Wieschollek Amazon 图宾根, 图宾根, 德国

Hendrik P. A. Lensch 计算机图形组，图宾根大学，图宾根，德国

出版信息

期刊: IEEE Transactions on Big Data 年份: 2023 卷: 9 期: 1 页码: 267-279 DOI: 10.1109/TBDATA.2022.3161156 文章编号: 9739943 ISSN: Electronic ISSN: 2332-7790, CD: 2372-2096

指标

论文引用: 27 总下载量: 1976

资金

• 德国研究基金 (拨款: 390727645 和 SFB 1233)

• 德国联邦教育与研究部 (拨款: 01IS18039A)

关键词

IEEE 关键词: 图形处理单元, 索引, 量化（信号）, 最近邻方法, 搜索问题, 并行处理, 大数据

关键词： 最近邻搜索, 邻域搜索, 结构索引, 计算机视觉系统, 最近邻图, 分层构造, 快速查询, 并行化, K最近邻, 层层递进, 底层, 较低层, 停止准则, 邻近点, 召回率, 数据点集合, 图构建, 最近邻, 基于图的方法, 出边, 分层图, 逆链接, 查询时间, 优先队列, 查询点, 高召回率, 向量量化, 最近点, 边列表, 定向图

作者关键词： 最近邻搜索, 图和树搜索策略, 信息检索, 近似搜索, 相似搜索, 大数据

未定义

第 1 节 引言

近似最近邻（ANN）搜索在包括数据库、计算机视觉、自动驾驶、个性化医疗和机器学习等各个领域，发挥着至关重要且长期存在的作用。随着收集海量数据变得更容易，构建可扩展且高效的数据结构以检索相似项目已成为一个活跃的研究课题。尽管近期取得了所有进展，但在高维空间中保证检索到精确最近邻的唯一可用方法仍是穷举搜索，原因是维度灾难 ¹。即使利用现代硬件，对数十亿高维数据点进行穷举搜索仍不切实际。相反，大多数流行的方法通过搜索可能为最近邻的条目来放宽问题，接受最小的准确率损失。

除了设计非常快速的基于 GPU 的近似 kNN 查询算法之外，我们着重于高效构建分层图结构搜索方法。构建时间在动态增长或变化的数据集中用于实时分析时变得越来越重要，例如在视频中用于跟踪和目标识别的对应与特征匹配、类似 DEEP1B ² 的神经网络新嵌入向量，或在推荐系统 ³ 中。我们的图构造方法显式地以高概率确定数据集中每个点的真实 k 个最近邻。解决此全局任务在 n-体问题中非常相关，例如显著点估计、核密度计算、聚类分析、更鲁棒原型检索，或嵌入中的特征匹配。

为了跟上每天产生的数据规模，现代方法使用高度定制的索引结构，充分利用GPU的大规模并行性 ⁴, ⁵, ⁶, ⁷ 或定制硬件 ⁸，与以前的基于CPU的方法 ⁹, ¹⁰, ¹¹, ¹², ¹³, ¹⁴, ¹⁵, ¹⁶。

召回质量在很大程度上取决于搜索结构的选择以及执行的搜索（查询）本身。基于量化或哈希/分桶方案 ¹⁷, ¹⁸, ¹⁹, ²⁰, ²¹, ²², ²³, ²⁴, ²⁵, ²⁶, ²⁷ 可以高效构建，但通常由于在高维空间枚举并访问相邻单元格是耗时的，召回率相对较低。最近，通过图基方法 ²⁸, ²⁹, ³⁰, ³¹, ³², ³³, ³⁴, ³⁵, ³⁶ 实现了更高的召回率。构建有效搜索图的现有方法，例如 ³⁷，以顺序方式更新可变大小的边列表。这些方法高度依赖全局内存同步，难以在几个核心之外有效并行化。因此，它们的构建时间增长不良，通常以小时甚至几天计量 ³⁸, ³⁹.

给定预先计算好的图结构，查询会遍历图的边以缩短到查询点的距离。 它需要计算当前被检查节点的所有邻居的距离，移动到下一个最佳点，并记录已访问的点。 所有决策都是局部且独立进行的，使得查询算法成为并行化的理想候选。 然而，想要实现高效的并行化，需要仔细解决若干问题。 例如，加载每个向量进行比较时可用的内存带宽可能成为瓶颈。 在这里，Optane 内存 ⁴⁰ 或 GPU ⁴¹ 提供了解决方案。 其次，在 GPU 上，需要应对在存储已访问点列表时每线程或每块可用内存有限的问题。

因此，我们提出了一种面向 GPU 的查询设计，基于线程块级别，具有高度的片上资源利用率，利用完全并行的多用途缓存和固定数目的邻居。进一步地，我们引入了一种新技术，实现了非常快速的图构建，该技术利用快速并行查询算法迭代合并多个子图。该自下而上的构建方案如图 1 所示。层次化图被用作全局优化替代方案，以克服局部连通性中的缺口，尤其是在构建期间。此外，我们的局部对称链接方法减少了图中冗余链接的数量，以规避受内存受限缓存溢出的负面影响。

图 1。对数据集 (a) 的 kNN-图自下而上构建的示意图。随机划分后 (b)，为每个划分 (c) 构建 kNN-图。 一组节点 (d) 构建更粗的 kNN-图，用于在划分之间传播链接。这些链接用于合并几个划分 (e) 成最终的 kNN-图 (f)。

我们的方法也天然适用于批处理，因为它可以同时生成多个子图。通过放弃将多个子图合并为一个整体图的最终步骤，可以轻松获得针对大型数据集各部分的独立但有效的子图，否则这些子图可能无法放入内存。它们甚至可以在多块 GPU 上同时处理，每个查询只需在每个分片上执行一次。该简单而有效的方法实现了多 GPU 的最佳利用。

总而言之，我们的主要贡献是提出了一种在 GPU 上对高维数据进行极快近似 kNN 搜索的方法。我们不仅关注快速查询时间，还关注索引结构的高效构建，同时仍能实现对真实最近邻的高召回率。

从我们的经验评估可以看出，所提出的方案在构建时间和查询时间上均优于现有方法。与此同时，召回率始终保持在较高水平，并且可以进一步降低构建或查询时间以换取更快的速度。我们提出的多 GPU 方案能够在包含数十亿条高维条目的常见基准数据集上实现超过 99% 的召回率。

第 2 节 相关工作

大量文献关注加速最近邻搜索的结构设计。除传统方法 ⁴²、⁴³ 之外，最受欢迎的技术要么依赖于聚类中的数据量化 ⁴⁴、⁴⁵、⁴⁶、⁴⁷、⁴⁸、⁴⁹、⁵⁰、⁵¹、⁵²、⁵³、⁵⁴，要么构建邻域图 ⁵⁵、⁵⁶、⁵⁷、⁵⁸、⁵⁹、⁶⁰、⁶¹。为实现最高性能，这些方法大多数为每个条目计算压缩表示，因为大型数据集无法适入高速内存。存在几种策略来计算这种压缩。虽然哈希方法 ⁶²、⁶³、[^31] 产生紧凑的二进制码，但基于量化的方法通过将每个数据点分配给其所属的质心来重新使用质心，从而为每个数据点分配唯一标识符。经验表明，量化方法比各种哈希方法 ⁶⁴、⁶⁵ 更准确。

量化方法 用于最近邻搜索的聚类方法最早由 Jégou et al. ⁶⁶ 普及，最初在 [^32] 中提出。 这类索引结构，例如 IVFADC ⁶⁷，将高维搜索空间划分为由向量量化（VQ） [^33] 获得的一组质心描述的互不相交的 Voronoi 单元。随后，Babenko et al. ⁶⁸ 将这一思想扩展到将高维向量空间分解为正交子空间的情况。在此，每个向量在每个子空间中根据该子空间内的独立码本独立分配给一个质心。Wieschollek et al. ⁶⁹ 提出了码本的层次化表示，并使用 GPU 展示了更优的性能。Johnson et al. ⁷⁰ 将 IVFADC ⁷¹ 迁移至 GPU，并结合快速的基于 GPU 的 k 选择实现，即从给定列表中返回最小的 k 个元素（量化方法的关键部分）。他们是首批通过复制和分片使用多 GPU 并行化的工作。他们的工作形成了库 “FAISS”。最终，Chen et al. ⁷² 提出了一种基于 GPU 的方法 RobustiQ，克服了 FAISS 的内存限制，通过以层次方式扩展 ⁷³ 的线量化思想。仍然，报告的距离仅是真实距离的近似。

所有基于哈希和量化的索引方案都存在相同的问题，即它们将空间划分为单元格。虽然查询所在的单元格可以非常高效地找到，但精确最近邻可能位于相邻单元格的边界之外。高维中确定并访问所有相邻单元格是严重限制这些方法的问题。

kNN-graph 基于方法是加速查询过程的另一种方式。我们提出的方法属于此类。核心思路是将搜索空间中的每个点与其附近点的 k 连接起来。每一次查询都会从数据集中随机猜测一个点开始。然后，通过用来自 k 关联邻居点的更好点来替换原始猜测，从而对猜测进行细化。Chen et al. ⁷⁴ 提出了一个快速分治策略来计算此类 kNN-graph。Done et al. ⁷⁵ 引入了 NN-descent，用 kNN-graph 加速 NN-search。通过此方式，每个点维护其自身最近邻列表以及将其视为最近邻的点列表。此方法随后被扩展 ⁷⁶，以利用 MapReduce。EFANNA 作为多层次索引结构，使用截断的 KD-tree 构建 kNN-graph ⁷⁷。

在理想情况下，增添额外链接的 kNN-graph 可以保证对于任意起始点，NN-descent 能收敛到正确解。以大规模计算这样一个带有额外链接的图是不可行的。因此，存在若干方法至少可以近似此类图 ⁷⁸, ⁷⁹。Fu et al. ⁸⁰ 将 NSG 作为一种近似方法引入。为了降低整体边数，他们的优化尝试为每个节点单独降低出度。该方法可以扩展到多核心之外，在基准数据集上超过 GPU 方法 ⁸¹。Harwood et al. ⁸² 建议了一种构建此类图的替代方法。从相对稠密的图开始，他们移除“阴影边”，这些边在查询过程中考虑遍历路径时是冗余的。他们展示了使用 GPU 的有前景结果，但仅在相当小的数据集上，因为构建时间相当高。Malkov et al. ⁸³ 构建了一个层级图结构以加速最近邻搜索。

对于基于图的方法，内存吞吐量往往是限制因素。Ren et al. ⁸⁴ 提出了在异构内存上对离线数据集构建 HNSW 风格搜索图的优化方法。使用快速 Optane 内存使他们能够快速查询即使是十亿规模的数据集并保持高精度。Zhao et al. ⁸⁵ 提出了基于 GPU 的“搜索图” (SONG)，使用以 HNSW ⁸⁶ 或 NSG ⁸⁷ 构建的索引结构，在大多数情况下实现了显著的速度提升，相较于基于 CPU 的查询。

我们的方法与 HNSW ⁸⁸ 最为相似，采用其分层构造，但我们对构造任务的并行性进行了精细调优，并在查询阶段也有所不同。

第 3 节 背景

在本节中，我们正式介绍近似最近邻（ANN）问题描述及所使用的符号。

3.1 最近邻搜索

最近邻问题检索一个点 x^\star，该点来自数据集 \mathcal {X}=\lbrace x_{1},\ldots,x_{n}\rbrace，且与查询 q 的距离最小。为了简单起见，本文假设欧氏空间 ({\mathcal {X}\subset \mathbb {R}^{d}}, {q\in \mathbb {R}^{d}}) 与欧氏距离 (\Vert \cdot \Vert _{2})。因此，q 的最近邻 x^\star \in \mathcal {X} 定义为

\begin{equation*} x^\star = \mathop{\arg\min}_{x\in \mathcal {X}} \left\Vert q-x \right\Vert _{2}. \tag{1} \end{equation*}

同样，k-最近邻搜索在给定查询时检索来自 \mathcal {X} 的 k 个最近条目。由于寻找精确最近邻可能代价高昂，我们可以接受 \mathcal {X} 中与 q 接近的点，从而得到等式 (1) 的近似解。

3.2 kNN 图

在 kNN 图中，来自数据集 \mathcal {X} 的每个点 x 代表图 G 中的一个节点。此外，我们将 \mathcal {N}_{x}\subseteq \mathcal {X} 定义为包含 k 个元素的 x 的局部邻域，并将构造 \mathcal {N}_{x} 的细节留待下一节讨论。图的边 E 随后定义为 (x,y)，其中 y \in \mathcal {N}_{x}。请注意，得到的图是一个有向图 G=(\mathcal {X}, E)，其中 E=\lbrace (x,y)\;|\;x\in \mathcal {X}, y \in \mathcal {N}_{x}\rbrace 与 (x,y) \in E \nRightarrow (y,x) \in E。

一种寻找查询点 q 最近邻的贪心算法是 NN-descent ⁸⁹。从初始猜测 {x\in \mathcal {X}} 开始，计算 q 与每个相邻点 y\in \mathcal {N}_{x} 之间的距离。如果任何 y\in \mathcal {N}_{x} 比 x 更接近 q，则用来自 \mathcal {N}_{x} 与 q 之间最近的点替换猜测 x。该过程迭代进行，直至 \mathcal {N}_{x} 中没有点比 x 与 q 的距离更小。然而，当前的 x 可能无法指向正确的搜索方向，这种贪心算法可能会在纯 kNN 图上陷入局部最优。

3.2.1 常见陷阱

由于 NN-descent 是一种贪心搜索，它无法保证找到精确解。下面列出了一些原因：

Connectivity: 作为 kNN 图是有向图，y 可能直接连接到 x，成为其最近邻，从而 {y\in \mathcal {N}_{x}}。但这并不意味着存在逆向链接 ({y\in \mathcal {N}_{x} \nRightarrow x\in \mathcal {N}_{y}})。因此，构建增广（多样化）的 kNN 搜索图需要处理同步出边和入边（逆向）。

Gaps in high-dimensional spaces: 由于每个点仅与有限数量的局部邻居相连，甚至在 2D 中也存在病态情况，即附近的点根本不直接相连。图 3 展示了这种情况。由于存在间隙，真正的最近邻将无法被找到。计算理想化的单调相对邻域图 ⁹⁰（MRNG）可以避免此问题，但需要高度变化的连通性，不适合并行方法，且会增加额外的计算负担。

Fig. 2. 我们的缓存由最佳列表、prioq（优先队列）和访问列表组成。它完全驻留在共享内存中。最佳列表和 prioqboth 包含索引和距离，并按距离排序。访问列表仅包含索引以节省内存。prioq 和访问列表实现为环形缓冲区。这样可以轻松从 prioq 前端弹出元素，并在访问列表已满时覆盖旧元素。整个线程块以并行方式访问和维护缓存。

图 3. 允许一个 slack \xi 使得能够逃离一个局部最小 x\in \mathcal {X}，最终达到给定查询 q\in \mathbb {R}^{d} 的解 x^\star \in \mathcal {X}。在此边界之外的点不太可能提供有用链接，并被丢弃以降低计算成本。（右）使用我们的停止准则 (\tau _{q}) 与使用不断增长的最佳列表终止查询的比较。使用最佳列表方法，只有在与高内存使用相结合的情况下才能实现高召回率，这会减慢查询速度。

节点度: 在为任何 x\in \mathcal {X} 选择 \mathcal {N}_{x} 的基数时存在权衡。 较少的边会放大之前描述的问题，但也减少了每一步所需比较的数量。 相反， 较多的边允许贪心搜索逃离局部邻域，但增加了每次迭代的成本。*

第 4 节 基于 GPU 的最近邻搜索

搜索 k 个最近邻，对于多查询，给定某些图结构，是各种应用的核心操作，也是我们图构建（见第 5 节）的主要构件。 在极短时间内实现高召回率是我们基于 GPU 的并行 kNN 图结构搜索算法的主要目标。 该算法可以在一定范围内根据质量或速度进行调优，提供一种面向广泛使用场景的解决方案，满足需要高召回率的需求以及对质量约束较低的实时算法。

主要思路是通过为每个查询使用一个线程块来高度并行化搜索。 与每个线程对应一个查询的朴素方案不同，主要优势在于将足够多的片上资源捆绑在一起，使所有元数据都能保存在极快的内存中。这一点尤为重要，因为基于图的方法仍需要从全局内存加载大量邻域信息以及向量用于距离计算。 此外，线程块方法通过非常高效的合并内存访问保证了高内存带宽。 它还允许在并行中执行更多计算，因为诸如距离计算、维护优先队列和访问列表等通用任务可以并行化。 此外，运行时间各异的单个查询可以独立调度。

4.1 基于 GPU 的搜索与回溯

假设一个多样化的（参见第5.2节）kNN图，并给定起始点 s \subset \mathcal {X}，对于查询 q\in \mathbb {R}^{d}，执行来自算法1的简单贪心下坡搜索并回溯。首先，缓存结构（参见第4.1.1节）使用查询点和一个松弛因子 \tau（参见第4.1.2节）进行初始化（init）。随后，通过 fetch 将起始点 \mathbf {s} 引入缓存，该过程会计算它们与查询 q 的距离并将它们加入优先队列 (prioq)。作为起始点 \mathbf {s}，我们使用层次图顶层的节点（参见第5.4节）。

直到优先队列中没有更多未探索的点，最近未访问点 a 的所有邻居 \mathcal {N}_{a} 被抓取到缓存中。基本上，这相当于在图中执行深度优先搜索。我们的缓存结构管理一个按距离排序的列表，记录在遍历过程中观察到的与查询最近的 k 个点 (best)。因此，best 列表作为搜索结果返回。

4.1.1 GPU 上的缓存

我们快速基于 GPU 的 kNN 搜索的核心是一个多用途缓存（参见算法1和2）。GPU 的主要缺陷之一是其受限的片上内存（register 和 shared memory1），访问时具有低延迟。

尤其是 kNN 图算法对高度动态的数据结构有强烈需求，例如不可预测增长的待访问潜在点列表或已访问点列表。这些元数据在查询过程中会被频繁查看和修改。

缓存的内存布局如图 2 所示。它由三个主要部分组成：

1. best: 一个按距离排序的列表，列出离查询最近的点及其距离。

2. prioq: 一个优先队列，按距离排序的环形缓冲区，用于管理待访问的点。

3. visited: 一个环形缓冲区，以先进先出的（FIFO）方式缓存已访问点的索引。

这三个部分都在 shared memory 中处理。其总长度是已分配线程数的整数倍，因此，每个线程都有多个工作项。

Algorithm 1. Basic Query With Backtracking

Function query(G, \mathbf {s}, q, \tau, k):

Input: search-graph G with start points \mathbf {s}, query point q, slack factor \tau(see Section 4.1.2)

Output: k closest points to q

cache.init(q, \tau) /(see Section 4.1.1)/

cache.fetch(\mathbf {s})

while (a \leftarrow {cache}.\tt {pop}()) \ne \emptyset:

cache.fetch(\mathcal {N}_{a}) /(see Section 3.2)/

return cache.best

我们的缓存主要方法如算法2所示，并在随后的段落中进行描述。请注意，为了可读性方便，已省略防止竞争条件的同步屏障。我们将更多信息发布在公开的开源代码2中。为便于可视化，shared memory 变量用下划线表示，而普通变量假设存放在 register 空间。

Fetch. 给定一个点建议列表 \mathbf {p}，首先从建议列表中移除已知元素。每个建议与每个线程的工作项并行比较，若匹配则移除。剩余的建议逐步处理。到查询点的距离在并行中计算（dist）。每个线程从内存读取其相应的向量元素（s）并计算逐元素结果。随后进行归约得到完整距离。对于像归约这样的并行原语，我们使用 NVIDIA 的 CUB3 库进行高度优化实现。并行合并加载和处理在 GPU 利用率方面非常有效。满足我们条件的点会被推入缓存结构。

Push. 对于给定的索引对 p 和距离 d，pushmethod 在 best 和 prioq 的距离排序列表中执行并行插入。
为执行插入，所有索引为 c_{i} 且距离大于 d 的项被临时复制到线程块的寄存器中，并在未到达列表或环形缓冲区末尾时写回到后续索引 c_{i+1}。
新元素插入的位置是左侧项比新项更近的地方，或者在开始位置如果新项比所有先前项更近。
因此，符合 best 和 {prioq} 的点将同时插入两个列表。

由于 prioq 是一个环形缓冲区，逻辑起点和终点位置取决于头指针的位置。 因此，对物理边界的索引计算需要环绕处理。

Pop. 这个单线程过程返回优先队列的当前头部并管理环形缓冲区。
我们的 criteriais 在查询过程中单调递减（参见第4.1.2节）。
因此，如果 prioq 的头部违反 criteria，我们可以安全终止查询。
在有效情况下，点从 prioq 中移除并添加到 visited 列表的头部位置。
两个头指针向前移动一步。
最终返回该点。

Algorithm 2. Cache Operations

Function fetch(\mathbf {p}):

Input: Point proposals \mathbf {p}.

parfor {p_{c_{i}}} \in \lbrace \underline{best,{prioq},{visited}}\rbrace:

for p \in \underline{\mathbf {p}}:

if {p_{c_{i}}} = p:

remove p from \mathbf {p}

for p \in \underline{\mathbf {p}}:

d \leftarrow dist(p) /Compute in parallel./

if \tt {criteria}(d) \;:

push(p, d)

Function push(p, d): /Parallel insertion/

Input: Point proposal p with distance d.

parfor {p_{c_{i}}}, d_{c_{i}} \in \lbrace \underline{best,{prioq}}\rbrace:

/Read {p_{c_{i}}} and d_{c_{i}} and sync./

if d_{c_{i}} \geq d:

if \tt {is\_{n}ot\_{e}nd}(c_{i}):

\underline{p_{c_{i+1}}} \leftarrow p_{c_{i}}

\underline{d_{c_{i+1}}} \leftarrow d_{c_{i}}

if is_begin(c_{i}) or \underline{d_{c_{i-1}}} < d:

p_{c_{i}} \leftarrow p

d_{c_{i}} \leftarrow d

Function pop(): /Single-threaded routine/

Output: Returns head of priority queue.

p, d \leftarrow \underline{{prioq}_{head}}

if not \tt {criteria}(d):

return empty

/Remove point from prioq ./

\underline{{prioq}_{head}} \leftarrow {empty}

\tt {move\_{h}ead\_{f}orward}(head_{{prioq}})

/Add point to visited list./

\underline{{visited}_{head}} \leftarrow p

\tt {move\_{h}ead\_{f}orward}({visited}_{head})

return p

Function criteria(d):

return d \leq d_{best_{k}} + \xi /(see Section 4.1.2)/

4.1.2 停止准则

在高维数据上，仅依赖贪婪下坡搜索的算法很快会陷入局部最小值。
另一方面，完整回溯可能会遍历整个数据集。

一个常见的停止准则，例如 ⁹¹，是当最佳列表无法通过添加尚未访问的最近元素来改进时终止搜索，即一旦 d > d_{\mathrm{best}_{K}}，其中 d 是新元素的距离，d_{\mathrm{best}_{K}} 是最佳列表中最后一个元素的距离。为了获得更高的召回率，最佳列表需要扩展（K 需要增加），可能会多出数百个元素。

我们提出了一种有效的近似方法，即在最近的 k 近邻的距离上添加一个自适应、单调递减的松弛量 \xi：d_{\mathrm{best}_{K}} \approx d_{\mathrm{best}_{k}} + \xi，其中 k \ll K，这使我们能够将最佳列表的大小限制为仅查询的 k 最近邻（或至少 10）。与显式跟踪更远邻居的距离不同，松弛量考虑了安全边际，以确保最接近邻居的路径很可能被找到，例如图 3。搜索将在以下条件下终止

\begin{equation*} d > d_{\mathrm{best}_{k}} + \xi, \quad \xi = \tau \cdot \min \lbrace d_{\mathrm{best}_{1}}, d^+_{\mathrm{nn}_{1}}\rbrace . \tag{2} \end{equation*}

松弛因子 \tau 控制安全边际的大小。d_{\mathrm{best}_{1}} 是查询特定的，并将边际与当前找到的最佳匹配相关联，而 d^+_{\mathrm{nn}_{1}} 与所给数据库节点的密度相关。具体而言，d^+_{\mathrm{nn}_{1}} 提供了一个全局上限（用于捕获异常值），该上限在图构建过程中计算得到。它表示在当前处理的图子集 \mathcal {S} 内所有点中最近邻的最大距离

\begin{equation*} d^+_{\mathrm{nn}_{1}} = \max _{x \in \mathcal {S}} \left\lbrace \min _{y\in \mathcal {N}_{x}} \Vert x-y\Vert _{2} \right\rbrace, \text{where } \mathcal {S} \subseteq \mathcal {X}. \tag{3} \end{equation*}

使用我们的停止准则可以保持最佳列表的规模较小，从而减少执行查询所需的共享内存量。如图 3 所示，我们的停止准则即使在高精度下也能实现高效性。

\tau 的典型取值在 0 以上、2 以下。更大的值会提高准确性，但收益递减。

第 5 节 近似对称最近邻图构造

适当的基于 CPU 的 kNN 搜索图的构建通常在全局图上按顺序进行。边要么被附加（例如 ⁹²），要么被修剪（例如 ⁹³、⁹⁴、⁹⁵），一次一个。在此过程中，每个节点的边列表会有很大变化，从完全为空到所有可能点的完整列表不等。虽然这些全局优化方法能在 CPU 上生成高质量的图结构，但在快速 GPU 基于构建时，它们是不可行的。

我们提出了一种基于图层化kNN搜索图并行合并的并行图构建方法，如图1所示。通过将构建搜索图的任务拆分为可并行的小任务，我们能够充分利用GPU提供的海量并行性。接下来，我们将展示我们的并行图构建流程，随后详细说明层级查询流程，以及通过对称链接实现的图多样化与细化。最后，我们讨论如何最佳地执行最终查询和多GPU配置。

5.1 构建层级kNN图

我们的构建过程（算法3）通过递归合并更小的搜索图，采用自底向上的方式构建kNN搜索图。

Algorithm 3. Parallel Graph Construction

Function BuildGraph(\mathcal {X}, L, k, \tau _{build}):

Input: Dataset \mathcal {X}, number of layers L, number of neighbors per point k, slack factor \tau _{build}

Result: search structure graph

graph \leftarrow init(\mathcal {X}, L, k, \tau _{build})

for l_{top}\leftarrow 0 to L-1:

if l_{top}&gt; 0:

graph.select(l_{top})

for l_{m}\leftarrow l_{top}to 0:

graph.merge(l_{top}, l_{m})

graph.sym(l_{m})

Function graph.merge(l_{top}, l_{m}):

parfor z \in \tt {graph}.\tt {layer}(l_{m}):

/Use brute force if {l_{top}} = l_{m}./

b_{z} \leftarrow graph.query(z, l_{top}, l_{m})

\tt {graph}.\tt {layer}{(l_{m})} \leftarrow b

if l_{m} = 0:

graph.stats()

Function graph.sym(l_{i}):

parfor z \in \tt {graph}.\tt {layer}{(l_{i})}:

graph.sym_links(z)

为了初始化过程，我们将整个数据集 \mathcal {X} 逻辑划分为大小为 s 的小批次，例如 32。这些代表高度为 1 的层级搜索图。我们首先执行 mergeoperation，将每个点与其最近邻连接，初始化底层的每点 k 条出边。随后，symoperation 在尝试逼近无向图的过程中，最多替换 k_{sym} 条出边，详情见第5.2节。

为了合并单个子图，我们首先从每组 g 个图中选择s 个点进行合并。选定的点随后形成新的顶层批次。在那里，我们执行与底层相同的操作。我们进行合并，即查询最近邻以填充出边列表并执行图多样化（sym）。由于任何点的最近邻可能出现在任何子图中，跨批界限的边将被引入。这些步骤随后自顶向下重复，直至整个层级搜索图相互连通。

每当到达底层时，我们还会为每个点保存到最近邻 d_{\mathrm{nn}_{1}} 的距离，并计算整个数据集（统计）的均值和最大值。这使得我们的停止准则可以轻松适配每个数据集，无需任何预处理。最初，最大值易受仍然粗糙的最近邻图中的异常值影响。因此，在构建过程中，我们将公式 (2) 中到最近邻 d^{+}_{\mathrm{nn}_{1}} 的最大距离替换为均值 \bar{d}_{\mathrm{nn}_{1}}。

\begin{equation*} \bar{d}_{\mathrm{nn}_{1}} = \frac{1}{|\mathcal {S}|} \sum _{x \in \mathcal {S}} \left\lbrace \min _{y\in \mathcal {N}_{x}} \Vert x-y\Vert _{2} \right\rbrace, \text{where } \mathcal {S} \subseteq \mathcal {X}. \tag{4} \end{equation*}

在为顶层选择点时，采用以 d_{\mathrm{nn}_{1}} 为权重的加权抽水站抽样，并使用方法 [^34]。

Algorithm 4. Hierarchical Query

Function graph.query(z, l_{top}, l_{m}):

Input: query point z from layer l_{m}, start layer l_{top}, and end layer l_{m}

Output: k closest points to z

cache.init(z, \tau)

\mathbf {s} \leftarrow getTopSegment(z, l_{top})

cache.fetch(\mathbf {s})

for l_{i} \leftarrow l_{top}-1 to l_{m}:

cache.transform(l_{i})

while (a \leftarrow {cache}.\tt {pop}{()}) \ne \emptyset:

cache.fetch(\mathcal {N}_{a})

return cache.best

由于所有构造任务可以在每一层的每个点上并行执行，并且每个任务只需要少量、有限的内存，利用GPU提供的大规模并行性时，构造过程可以相当快速地完成。

层次化 kNN 图查询

在顶层，mergeoperation（合并操作）可以简单地在每批的 s 个点之间执行暴力搜索。随着每向下层数的增加，批次数按因子 g 成长。为了在下层高效地搜索最近邻，我们执行层次查询（算法 4），该算法逐层利用已合并的上层来寻找进入下层批次的入口点，其它方面与之前提出的简单查询（第 4.1 节）相同。上层找到的最近点的索引随后被转换为下层相同点的索引，搜索持续进行，直到到达目标层 l_{m}。虽然已访问点的距离可以重用，但它们在下层的邻域会变化。因此，我们允许在层之间切换后再次访问所有点。

与 HNSW ⁹⁶ 一样，层次结构可以弥补连通性中的空缺，因为来自顶层的多个入口点可能从不同侧面接近底层的查询。

5.2 图的多样化

为了能够从任意方向到达任意点，图的每条边原则上应为无向边。然而，当每个点至少需要知道其 k_\text{nn} 个最近邻时，图中每点的总边数 x 在无向图中会有显著变化，因为将 x 作为最近邻的点的数量会严重依赖于局部几何。

为了获得规则的表示并允许每一步具有恒定工作量的简单并行遍历，我们的图仅包含恰好 k 条有向（即出向）边。我们将出向边逻辑上划分为至少 k_\text{nn} = k/2 条真正的最近邻和至多 k_\text{sym} = k/2 条逆向链接，用以近似无向图。

由于可表示的反向链接数量有限，需要确定哪些反向链接是必要的。Harwood 和 Drummond ⁹⁷ 引入了被查询的贪婪探索策略所使冗余的影子链接概念。对整个图进行优化以移除所有可能的影子边需要复杂的全局优化。构造单调相对邻域图也同样适用 ⁹⁸。

我们针对图的多样化的做法是通过对每个点 z 从其所有 k_\mathrm{nn} 最近邻 x_{i} \in \mathcal {N}_{z}^{nn} 在一个小搜索半径内进行查询，显式搜索缺失的反向链接。若存在从 x_{i} 回到 z 的直接反向链接，查询可以直接跳过。当在允许范围内不存在路径时，该链接会被添加（例如图 4）。这些搜索在所有点 z \in \mathcal {X} 上并行执行，从而实现更快的构造。

图 4. 维护对称链接。如果无法轻易找到从 x\in \mathcal {N}_{z}^{nn} 回到 z\in \mathcal {X} 的连接，边 e 被添加以允许在 z 与 x 之间传播最近邻信息。（右）在探测是否插入对称链接时，我们不考虑完整搜索半径，而是将要访问的点的最大距离限制在以中点 q_{m} 为中心的较小球内。

Algorithm 5. Symmetric Linking Query

Function graph.sym_links(z):

Input: symmetric query point z

for each x_{i} \in \mathcal {N}^{nn}_{z}

cache.init(z, \tau)

cache.fetch(x_{i})

while (a \leftarrow {cache}.\tt {pop}{()}) \ne \emptyset:

\mathbf {p} \leftarrow \mathcal {N}^{nn}_{a} \cup \mathcal {N}^{sym}_{a}

if z\in \mathbf {p}:

skip x_{i}

cache.fetch(\mathbf {p})

for each p \in {cache}.best:

if | \mathcal {N}^{sym}_{p} | < k_{sym}:

\mathcal {N}^{sym}_{p} \leftarrow \mathcal {N}^{sym}_{p} \cup \lbrace z\rbrace

break

详细的对称链接操作在算法5中展示。每个点 z 为自身发起查询，从其 k_\text{nn} 最近邻 x_{i} 开始。在查询过程中，只考虑每个访问点 \mathcal {N}_{x_{i}}^{nn} 的 k_\text{nn} 最近邻以及该点已插入的潜在对称/逆向链接 \mathcal {N}_{x_{i}}^{sym}，因为其它链接仍可能被覆盖。如果找到通往 z 的路径，搜索将继续使用 z 的下一个邻居。否则，在搜索过程中遇到的最近于 z 的点上插入指向 z 的链接，前提是该点的逆向链接列表仍有空闲容量。

为避免插入时出现竞争条件，我们使用原子操作来跟踪反向链接列表的大小。平均而言，这种方式所需的反向链接数少于 k/4。如果未找到候选，则忽略该链接。在我们的设置中，这种情况却很罕见，z 仍可能通过层级或多个起点被访问到。

5.2.1 附加对称链接约束

如图 4 所示，常规搜索空间将根据 z 和 x_{i} 定义。然而，为了生成能够为所有潜在查询点找到路径的搜索结构，我们进一步将其约束在仍需找到通往 z 的最坏情况查询上。因此，需要一个链接来弥合针对中点 q_{m} 的最坏情况查询的间隙。请注意，通往 x_{i} 的路径已给出，因为它直接从 z 已知。对于对称链接，仅此搜索空间相关，即由中心 q_{m} 与 x_{i} 的距离所定义的圆，但仍包含 z。在实践中，我们设置了 q_{m} = z + 0.4 \cdot (x_{i} - z)。这略微不那么保守，但减少了必要对称链接的数量。

5.3 图形细化

初始图构建可能并不总是在第一次尝试时产生完美结果。这一原因在某种程度上是由于在构建低高度且需要覆盖大规模数据集的搜索图时产生的 g 大合并因子。

在我们的实验中，我们发现使用高度为 L=4 的层级搜索图能提供最佳性能。要将最初的 n/s 个互不相连的子图（由单批大小为 s（通常是 s=32）的子图组成）合并为单一图，我们需要在每一层合并 g = \sqrt[L_1]{\frac{n}{s}} 个子图的组，每个新子图的最上层包含从这些 g 子图中采样的 s 个点（参见第 5.1 节）。对于 n = 256，每层只需合并 2 个图；而对于 n = 10^{6}，每层需要合并约 32 个图。子图数量 g 越高，进入下层的入口点就越少，限制了初始层级查询的成功率，因为每个合并后的子图只有 s/g 个入口点。对于 g > s，有些点只能在子图通过对称链接桥接后才能到达。

为了提升图质量，正如算法 6 所述的细化步骤可以执行，简单地在搜索图中重复合并和对称链接步骤。虽然细化步骤在实际子图合并期间也会有益，但我们观察到在最终阶段执行它们就足以保证搜索结构的整体质量。

Algorithm 6. Parallel Graph Refinement

Function RefineGraph (graph, l_{top}):

Input: search structure graph, top layer l_{top}

Result: refined search structure graph

for l_{m}\leftarrow {l_{top}}-1 to 0 \;:

graph.merge(l_{top}, l_{m})

graph.sym(l_{m})

5.4 查询注意事项

对于我们的方案，在图构建过程中，进行层次化查询至关重要，该查询会逐层搜索最近邻，因为搜索索引尚未完全合并。此时，粗到细的方法能够弥合尚未相连的子图之间的空隙，并为感兴趣的区域提供多条路径。从多个分散的起点开始显著提升质量。特别是，重要的不仅是 1-NN，还包括位于 k 远端的邻居。然而，对于已经收敛的搜索图，这种工作已经不再必要，因为所有点已相互连通。

在平面索引结构中搜索没有层次化开销。例如，Li et al. ⁹⁹ 总是从平面图中的质心开始查询。尽管如此，随着点数增加，跳转到质心的次数也会增加。此外，使用单一起点时，任何目标点都只会从一个方向接近。搜索可能容易出现空隙或链接问题。

在我们的设计中，最底层实际上是包含所有点的平面图。在对完成的搜索图寻找新点的最近邻时，实际上更有效的方法是跳过中间层，直接在底层继续搜索，在探索构成顶层的 s 起点后进行。这样可以显著减少搜索迭代次数，否则搜索需要在每个中间层上迭代。实际上，与层次化方法相比，我们没有观察到召回率的损失，而是显著节省了时间。

5.5 多 GPU

并行构建和搜索算法可以扩展到多 GPU。Johnson et al. ¹⁰⁰ 区分两种多 GPU 并行化方式：Replication 和 Sharding。Replication 将整个数据集 \mathcal {X} 复制到多个 GPU，以进一步并行化查询过程。查询 \mathcal {Q} 被均等分配给可用的 GPU，从而实现线性加速。

Sharding 将数据集 \mathcal {X} 分成更小、独立的分片。这使我们能够处理本来无法放入 GPU 内存的十亿规模数据集。必要时，分片也可以被调入主内存或磁盘。所有 GPU 并行构建各自分片的搜索图。由于每个分片的点数减少，复杂度降低，可实现相对于相同质量的超线性加速 w.r.t..

缺点是每个查询都需要处理所有分片。当每个GPU查询多个分片时，我们在后台将已处理的分片替换为新分片，以隐藏内存延迟。仍然，分片交换限制了每批查询的最短运行时间。作为额外开销，每个分片的单个查询结果需要合并。在每个GPU内部，我们使用并行基数排序。跨GPU的最终结果在CPU上使用高效的n路合并计算得到。

第6节 实证评估

在下面，我们将在若干公开可用的基准数据集上评估所提出方法及其各个组成部分的性能，并以时间和准确度的形式报告定性和定量结果。

数据集. 我们在不同应用场景下生成的各种规模和维度的数据集上进行了实验：SIFT1M ¹⁰¹ 和 SIFT1B ¹⁰²，包含维度为 128 的 SIFT 向量；DEEP1B ¹⁰³，拥有 10 亿个 96 维特征向量，编码完整图像；NyTimes [^35]、[^36] 和 GloVe 200 [^35]、[^37]，这两个偏斜且聚类的数据集包含随机投影的词嵌入，使用余弦相似度进行比较；最后是 960 维的数据集 GIST ¹⁰⁴。有关数据集和我们搜索图构建细节，请参见表 4。

表 1

表 2

表 3

表 4

硬件. 我们使用一台配备 8 块 NVIDIA Tesla V100 和 2 块 Intel Xeon Gold 5218 的机器，通常只使用单个 GPU，除非是 SIFT1B 和 DEEP1B，需要使用全部 8 个 GPU。我们在补充材料中发布了更多 GPU 的结果。

Performance Metrics. 当将结果与其他方法比较时，需要仔细关注所使用的度量指标。查询性能通常以召回率（R@k）来衡量。对于基于量化的方法（例如 ¹⁰⁵），召回率被理解为在前 k 个结果中返回真实最近邻的查询比例

\begin{equation*} R@k=\frac{\left|\mathcal {N}_{q}^\text{gt}(1) \cap \mathcal {N}_{q}(k)\right|}{\left|\mathcal {N}_{q}^\text{gt}(1) \right|}. \tag{5} \end{equation*}

对于使用精确距离计算的方法——例如基于图的方法——召回率被理解为前 k 个结果与前 k 个真实最近邻之间的重叠。为了解释清楚，我们将其称为共识（C@k）

\begin{equation*} C@k=\frac{\left|\mathcal {N}_{q}^\text{gt}(k) \cap \mathcal {N}_{q}(k)\right|}{\left|\mathcal {N}_{q}^\text{gt}(k) \right|}. \tag{6} \end{equation*}

由于我们的算法使用精确距离计算，真正的最近邻要么被报告为答案中的第一个元素，要么根本未被找到。因此，我们仅报告 R@1（=C@1）。

Batch Size. 每批执行的查询次数是基于 GPU 的查询中的一个重要因素，我们在图 8b 中进行了分析。在我们的实验中，我们测量了在一个批次中执行所有 10000 次查询（不包括 GIST ¹⁰⁶ 的 1000 次查询）的时间，并将总执行时间除以查询次数，以 \mathrm{\mu }\mathrm{s}/查询 的形式报告，或将其绘制为每秒查询次数。

Fig. 5. 各种数据集和前 k 个查询的性能比较。右上角的结果更为优越。我们主要与 SONG [3] 进行对比，采用其论文中的数值并使用相同的 GPU。在 SIFT1M 上，我们还与最先进的单核 CPU 基础方法 [20]、[21]、[26] 进行对比，并包含一种名为 ”GGNN-HNSW” 的配置，其中我们使用我们的算法来查询由 HNSW [20] 构建的图，类似 SONG [3] 的做法。我们的查询显著优于 SONG，并且在使用我们的方法以更短的时间构建类似规模的搜索图时，取得了相似的结果。查询 100 个最近邻或更复杂的数据集（如 GloVe 200 或非常高维的数据集如 GIST）时，也能实现高性能。在相对较小的 NyTimes 数据集上，我们的图构建似乎并非最优，但高度高效的查询仍然能够以显著优势超越 SONG。使用 8 台 GPU，即使是像 SIFT1B 或 DEEP1B 这样规模达十亿级的数据集，也可以以每秒约 100k 次查询的速率进行查询，并获得近乎完美的召回率。

Fig. 6. SIFT1M 搜索图构建时间的拆分。大部分时间花在合并操作（86.92%），部分时间在 sym 操作（13.06%），几乎没有时间用于选择上层的点（0.02%）。

Fig. 7. 在单张 GPU 上对 SIFT1B（最多 100M）逐步增大子集的构建时间和每秒查询次数。构建时间几乎与数据集大小呈线性关系。随着数据集大小的增加，查询性能在执行时间和准确度上都略有下降，前提是 slack 因子保持为常数 \tau _{q}。

Fig. 8. 查询性能既受搜索图质量影响，也受同时执行的查询数量影响。具有相同准确度的查询如果在构建上花费更多时间，则可执行得更快（a）。在这里，没有进行任何细化（r=0），以可视化\tau _{b}对初始构建的影响。通常，进行几轮细化迭代可以进一步提升查询性能。在查询规模（b）方面，已在几千个查询时达到高性能，而进一步的同时查询可获得更好的性能，峰值在95k查询。

6.1 性能比较

评估在默认配置 GGNN、速度更快、准确度更低的配置 GGNN^\ddagger 以及 8 GPU 配置 GGNN^{8}（参见表 4 的参数）上进行。

作为参考，我们使用了几种最近的基于 CPU 的方法 ¹⁰⁷、¹⁰⁸、¹⁰⁹，我们在 Intel Core i7-9700K 上执行了单线程参考实现。我们还与基于 GPU 的 SONG ¹¹⁰ 进行比较，并模仿其查询预构建 HNSW ¹¹¹ 图底层的做法，使用我们的查询作为 “GGNN-HNSW”。使用我们的查询甚至更快。此外，其性能与使用我们的方法构建的同等规模图查询非常相似，且时间显著更短。详细的性能比较见图 5 以及表 1、表 2 和表 3。在这些表中，我们与之前公布的结果进行比较，其中 GPU 基础的方法 ¹¹²、¹¹³、¹¹⁴、¹¹⁵ 使用了 NVIDIA GTX Titan X GPU，¹¹⁶ 则使用了 Arria 10 GX1150 FPGA。除了在所有数据集上显著更快（在 SIFT1M 上每查询约 1\mathrm{\mu }\mathrm{s}），我们的方案还能实现非常高的召回率，接近完美。

6.2 搜索图构建

下面，我们检查构建过程的几个方面，包括各个构建步骤所花费的时间、数据集规模的影响、每点最近邻数所决定的图质量，以及如何将额外的构建时间换取更快的查询。

6.2.1 构建时间

我们方法的构建时间和索引大小列在表4中。比较之下，FAISS ¹¹⁷ 报告在DEEP1B上构建时间为4到24小时，且R@1不到50%。HM-ANN ¹¹⁸ 报告在有效十亿规模搜索图的构建时间约为100小时。使用我们的分层GPU基础图合并算法，可以在DEEP1B上实现99%的R@1，甚至在SIFT1B上实现100% R@1，且查询速度快，构建时间不足2小时。

6.2.2 构建时间组成

图6显示了使用2次细化迭代时各个图构建操作的耗时。构建时间的大部分用于合并操作，尤其是涉及底层的合并，合并操作为数据集中的所有点搜索k最近邻。

6.2.3 数据集大小

高效的图构建需要随着数据集大小良好扩展。如图7所示，构建时间几乎与数据集大小呈线性关系，\approx O(n^{1.077})。这可以通过大部分构建时间花在独立确定每个底层点的邻居（参见第6.2.2节）来解释。此几乎线性行为远优于暴力kNN构建的复杂度 O(n^{2})。

6.2.4 全部查询

从零开始快速构建kNN搜索图还解决了另一个有趣的问题，即为数据集中的所有点计算k最近邻，类似于n体问题中经常遇到的情况。当我们构建完整层次结构时，最终的合并步骤实际上为所有点搜索k个邻居。在表5中，我们展示了考虑一致性时全查询问题的质量。参考图7，这个全查询问题再次表现出近乎线性的行为。然而，在分片的情况下，所有点都需要一次性对每个分片进行测试。由于分片数量与点数呈线性关系，人们又会接近O(n^{2})的复杂度，尽管常数很小，例如SIFT1B数据集使用16个分片。

表5

6.2.5 构建-查询权衡

我们的图构造算法和查询可以根据速度或准确性进行调优。构建时间由松弛因子 \tau _{b} 以及执行的细化迭代次数 r 控制。构造时间越长，得到的图越精确。快速组装的图的边质量更差，查询可能需要访问更多节点，直到满足停止准则。图 8a 显示了固定召回率下构建时间与查询时间之间的折衷。

6.3 查询行为

查询的运行时间和质量可以通过调整松弛因子 \tau _{q} 来控制停止准则。正如表 1 所示，增加 \tau _{q} 时，查询时会考虑更大的安全余量，从而获得更好的召回率，但需要访问更多点，导致查询时间更长。

观察查询随时间的变化是很有启发性的。在图 9 中，查询点到起始点（即顶层最近点）的初始距离在仅经过少量迭代后已被大幅降低。这里一次迭代指的是从优先队列中取出最佳点，并计算其与所有邻居的距离。大部分时间用于仔细探索真正最近邻周围的邻域。快速定位最佳候选点后，查询会被停止准则终止，以避免不必要的迭代。这种效果不仅在绘制的查询距离子集里出现，在所有查询的直方图中也能统计体现。

图 9。观察若干查询的行为（a），可以看到搜索图很快就找到了大致区域。随后，探索局部邻域，并在发现最后一次改进（由标记指示）后不久，查询会被停止准则终止。停止准则的有效性也体现在统计（b）中。总迭代次数的分布与实现最终改进所需的迭代次数分布非常接近，仅落后几次迭代。

6.3.1 超出 GPU 内存的查询

在对十亿级数据集进行查询时，即使在8块 NVIDIA Tesla V100 系统上，所需的 GPU 内存也会迅速超过可用内存。虽然 SIFT1B 与低占用图 \text{GGNN}^{8\ddagger } 仍可放入 GPU，但使用 \text{GGNN}^{8} 图时，超出了可用内存 2 块 (4.2 GiB)。在 DEEP1B 上，单是数据集就已经超过可用内存，且使用 \text{GGNN}^{8} 时，每个 GPU 在每次查询传递中还需要加载额外的 28 GiB。由此产生的限制由主机到设备的内存吞吐量 (\approx 12 GiB/s [^38]) 定义，即对于 10k 次查询，这在 SIFT1B 上至少为 35 \mathrm{\mu }\mathrm{s} 查询，在 DEEP1B 上为 233 \mathrm{\mu }\mathrm{s} 查询。这些界限如图 5 所示。请注意，这种加载时间可以通过执行更耗时的整体查询完全掩盖，例如使用更多查询、增加 \tau _{q} 或更大的缓存。为了与未来在具有足够内存的设备上提出的方法进行简易比较，我们还报告了不考虑内存传输的计算时间。

第 7 节 结论

我们提出的并行基于 GPU 的搜索算法在速度上大幅超过所有最先进的算法，并且在保持 99% 以上召回率的同时，代表了最快的 ANN 查询技术。高效的查询算法进一步加速了子图的并行构建和合并。我们的层次化构建方案生成高质量的 kNN 图，并通过图多样化链接实现非常高效的遍历。它可以轻松部署在多 GPU 系统中，以应对超大规模数据集。它是首个能够在不到一小时内为十亿级数据集构建有效搜索结构（R@1 \geq 0.99）的 ANN 搜索方法。对于百万级数据集，足够质量的搜索图往往可以在几秒钟内构建完成，从而在更大型的基于 GPU 的算法中（例如机器学习应用）也能快速完成最近邻搜索，包括在中间数据结构上。

目前，我们的方法对所有已访问的高维点计算精确距离。由于距离计算次数占据了查询时间的主要部分，采用数据向量的压缩表示可能进一步提升速度。

脚注

. https://docs.nvidia.com/cuda/ .

. https://github.com/cgtuebingen/ggnn .

. https://nvlabs.github.io/cub/ .

. 我们的方法 GGNN ^{8} 使用了 8 张 GPU。RobustiQ ¹¹⁹ 使用了 2 张 GPU。除此之外，还使用了单个 CPU 或 GPU。我们的方法实现了完美的 recall@1。GGNN ^{8} 的性能受限于主机到设备的内存带宽，否则它可以以 99% recall@1 在仅 24.5 \mathrm{\mu }\mathrm{s} /查询（见第 6.3.1 节）完成查询。较小的 GGNN ^{8\ddagger } 可以更快地查询，因为它遍历的分片更少，并且能一次性装载到 GPU 上。

. 我们的方法 GGNN ^{8} 使用了 8 个 GPU。FAISS ¹²⁰ 使用了 4 个 GPU。RobustiQ ¹²¹ 使用了 2 个 GPU。否则，使用单个 CPU。GGNN ^{8} 的性能受限于主机到设备的内存带宽，至少为 233 \mathrm{\mu }\mathrm{s} /查询（见第 6.3.1 节）。为显示 \tau _{q} 的影响并与未来硬件配置进行比较，我们报告在不进行目前必要上传的情况下的时间，作为 GGNN ^{8\star } 。

. 对于某些数据集，我们还演示了使用更快的构建版本（ \ddagger ）的构建-查询权衡。这里显示的所有配置都能达到至少 99% 的 recall@1。

参考文献

其他参考文献