论文名称：DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node

摘要

目前最先进的近似最近邻搜索（ANNS） 算法所生成的索引必须存储于主内存中，才能实现高召回率的快速搜索——这使得此类算法成本高昂，同时限制了数据集的规模。我们提出了一款名为DiskANN的全新基于图索引的搜索系统，它仅需64GB主存与一台普通固态硬盘（SSD） ，即可单机完成十亿级数据量的索引构建、存储与检索。
我们证实，DiskANN所构建的SSD基索引可同时满足大规模ANNS的三大核心需求：高召回率、低查询延迟、高密度（每个节点可索引的数据量） 。在十亿级SIFT1B数据集上，DiskANN在一台16核机器上的单秒查询处理量超5000次，均值延迟不足3毫秒，且1-recall@1高达95%以上。而当前类似内存占用下的十亿级ANNS算法（如FAISS与IVFOADC+P ），其1-recall@1效率仅止步于50%左右。此外，与HNSW、NSG等当前主流的图基方法相比，DiskANN在高召回率场景下，每个节点可索引与检索的数据量是它们的5-10倍。
最终，作为DiskANN完整架构的核心组件，我们提出了一款名为Vamana的全新图基ANNS索引，它的灵活性远超现有主流图索引算法——即使与全内存基的图索引相比亦是如此。

介绍

在最近邻搜索问题中，我们会得到一个由某一空间内的点集P构成的数据集。核心目标是设计一种轻量型数据结构，使其能够针对同一个度量空间内的任意查询点q以及给定的目标邻居数k，快速从数据集P中检索出q的k个最近邻。这不仅是算法研究领域的基础问题，也是计算机视觉、文档检索、推荐系统等众多领域常用的核心子程序。在这些应用场景中，图像、文档、用户画像等实际对象都会被嵌入到数百或数千维度的空间中，实体间的相似度需求将被编码为对应嵌入向量之间的距离度量。

遗憾的是，由于被称为维度灾难的现象，要实现精确最近邻检索，我们往往不得不对全量数据执行线性扫描相关操作。因此，我们通常转而采用近似最近邻（ANN）检索，其核心目标是返回尽可能接近最优解的k个邻居。更正式的定义如下：给定查询向量q，设算法输出的候选近邻集合为X（含k个向量），G为基准数据集中与q最相似的k个向量构成的真实最优集合。此时，集合X的k-recall@k精度指标可被定义为：

ANN算法的最终目标是在尽可能快地返回检索结果的同时最大化召回率，这就需要在召回率与延迟之间进行权衡。

针对该问题，目前已涌现出大量算法，它们采用各具特色的索引构建方法，在索引构建时间、召回率、查询延迟三者间呈现出不同的权衡取舍。例如，k-d树算法在处理低维数据时，可生成紧凑且检索速度极快的索引，但当数据维度d超过约20时，其检索效率会急剧下降。另一方面，基于局部敏感哈希（LSH） 的方法虽能在最坏情况下为索引规模与检索时间的权衡提供近似最优的理论保障，但这类算法无法充分利用真实数据的分布特性，因此在实际数据集上的性能已被近年来提出的基于图的检索算法超越。部分针对数据分布优化的LSH变体目前尚未在大规模数据集上验证其有效性。截至本文撰写时，在真实数据集上实现检索延迟与召回率最优平衡的算法是HNSW、NSG等基于图的算法：这类算法会在基础数据点上构建一张可导航图，检索时从一个指定（或随机）的起点出发，采用最佳优先遍历策略，沿着图的边逐步向查询点靠近，直到收敛到局部最优解。Li等人在文献中发表的综述对现有近似最近邻算法进行了全面且出色的对比分析。

诸多应用场景都要求在欧氏度量空间内对十亿级数据点执行快速且精准的搜索操作。目前，面向大规模数据集的索引构建主要分为两大类顶层方案。

第一类方案基于倒排索引+数据压缩架构，典型代表包括FAISS与IVFOADC+G+P 。这类方法会将整个数据集聚类划分为M个分区，检索时仅将查询向量与距离其最近的m个分区（m远小于M）内的数据点进行相似度计算。此外，由于全精度向量无法完全存入主内存，这类方法会采用积量化（Product Quantization）等量化方案对向量进行压缩。尽管这类方案的内存占用极低——存储128维十亿级数据点的索引仅需不到64GB内存——且借助GPU或其他硬件加速器可在5毫秒内返回结果，但由于采用的是有损压缩，其1-recall@1指标（召回率）仅为0.5左右。这类方法的1-recall@100指标表现更优，该指标衡量的是真实最近邻存在于返回的100个候选结果中的概率，但在许多实际应用场景中，这样的精度标准仍无法满足需求。

第二种方法是将数据集划分为互不相交的分片（shards） ，并为每个分片构建纯内存索引。然而，由于这类索引同时存储了索引结构和未经压缩的原始数据点，其内存占用远高于第一种方法（数据压缩方案）。例如，针对1亿个128维浮点向量构建的 NSG 索引，其内存占用约为 75GB。因此，若要为十亿量级的数据点提供检索服务，则需要多台服务器来分布式承载这些索引。据文献报道，阿里巴巴的电商平台淘宝就采用了这种方案：他们将包含20亿个128维向量的数据集划分为32个分片，并将每个分片的索引部署在不同的机器上。在该架构下，查询请求会被路由至所有分片，随后对各分片的返回结果进行聚合。淘宝报告称，该方法在延迟约为5毫秒的情况下，recall@100 指标可达 0.98。但值得注意的是，若要将此方案扩展到拥有数千亿数据点的互联网级规模，则需要耗费数千台机器。

这两类算法的可扩展性都受到了限制，因为它们构建的索引旨在由主内存（RAM）提供检索服务。将这些索引迁移到磁盘（即便是固态硬盘 SSD）会导致搜索延迟灾难性地增加，并伴随吞吐量的急剧下降。当前关于“搜索必须依赖主内存”的主流共识在 FAISS 的博客文章中得到了体现：“Faiss 仅支持从 RAM 进行搜索，因为磁盘数据库的速度要慢好几个数量级。没错，即便使用了 SSD 也是如此。”

事实上，磁盘驻留型索引（SSD-resident index）的搜索吞吐量受限于单次查询的随机磁盘访问次数，而延迟则受限于访问磁盘的往返次数（round-trips，每一轮往返可能包含多次读取）。一块廉价的消费级 SSD 处理一次随机读取大约需要几百微秒，每秒能支持约 30 万次随机读取。相比之下，具有多阶段流水线的搜索应用（如网页搜索）要求最近邻搜索的平均延迟必须控制在几毫秒以内。因此，设计高性能磁盘驻留型索引的主要挑战在于：（a）将单次查询的随机 SSD 访问次数减少到几十次；（b）将磁盘往返请求次数减少到 10 次以内，最好是 5 次以内。如果只是生硬地将传统内存 ANNS 算法生成的索引映射到 SSD 上，单次查询会产生数百次磁盘读取，从而导致无法接受的高延迟。

我们提出了 DiskANN，这是一种基于名为 Vamana 的新型图索引算法的磁盘驻留（SSD-resident）近似最近邻搜索（ANNS）系统。它打破了当下的固有认知，证明了即使是消费级 SSD 也能有效支持大规模 ANNS。
以下是我们研究工作的一些亮点：

高效性能：DiskANN 仅需在配备 64GB 内存的工作站上，即可为包含数百维度的十亿级（Billion-scale）数据点集构建索引并提供服务，其 1-recall@1（召回率）超过 95%，且延迟低于 5 毫秒。
Vamana 算法：该新型算法生成的图索引直径比 NSG 和 HNSW 更小，从而使 DiskANN 能够最大限度地减少磁盘检索时的顺序读取次数（注：指减少检索路径长度）。
内存检索表现：Vamana 生成的图也可直接用于内存检索，其搜索性能足以比肩甚至超越 HNSW 和 NSG 等最先进的纯内存算法。
索引合并能力：针对大型数据集重叠分区构建的小型 Vamana 索引可以轻松合并为单一索引，其搜索性能与针对整个数据集进行单次（single-shot）构建的索引几乎一致。这使得为原本内存无法容纳的超大规模数据集构建索引成为可能。
软硬协同架构：我们演示了 Vamana 可与积量化（Product Quantization）等现有的向量压缩方案相结合来构建 DiskANN 系统。在该系统中，图索引与全精度原始向量均存储在磁盘中，而压缩后的向量则缓存在内存里。

在下文中，我们用P表示包含n个数据点的数据集（即∣P∣=n）。我们考虑使用有向图来表示该数据集，图的顶点与P中的点一一对应，顶点之间存在有向边。为了简化说明，我们允许符号重载，即P同时代表数据集和顶点集，并将此类图记为 G=(P,E)。对于有向图中的任意一点p∈P，我们用Nout(p)表示与p关联的出边集合。最后，由xp表示点p对应的向量数据，并由d(p,q)=∥xp−xq∥表示点p与q之间的度量距离。本文所展示的所有实验均采用欧几里得度量（Euclidean metric） 。

Vamana图构建算法

在详细介绍 Vamana 的规范（见算法 3）之前，我们先简要概述基于图的近似最近邻搜索（ANNS）算法

鲁棒裁剪过程

如前所述，满足 SNG 特性的图都是 GreedySearch 搜索过程的良好候选对象。然而，这些图的直径（diameter）可能非常大。例如，如果数据点在单维实线上呈线性排列，那么满足 SNG 特性的将是一个直径为 O(n)的线型图，其中每个点仅与其相邻的两个邻居相连（端点除外）。在磁盘中搜索此类图时，为了获取算法 1 中搜索路径上所访问顶点的邻居信息，会引发多次磁盘顺序读取（sequential reads），从而导致高延迟。

为了克服这一问题，我们希望确保在搜索路径上的每个节点处，与查询点之间的距离都能以α>1的倍数因子递减，而不仅仅是像 SNG 特性那样单纯地递减。考虑这样一种有向图，其中每个点p的出邻域（out-neighbors）由算法 2 中的 RobustPrune(p,V,α,R) 过程确定。需要注意的是，如果每个点p∈P的出邻域都通过RobustPrune(p,P∖{p},α,n−1) 来确定，那么当α>1时，从任意起始点s开始的 GreedySearch(s,p,1,1)将在对数级（logarithmically）步数内收敛至 p∈P。然而，这会导致索引构建的运行时间达到 O~(n2)。因此，借鉴文献的思路，Vamana针对一个经过精心挑选且规模远小于n−1的集合V调用RobustPrune(p,V,α,R)，从而优化索引构建时间。

解释2：为什么用这种方式建立出边集合，在搜索路径上的每个节点处，与查询点之间的距离都能以α>1的倍数因子递减？
在上述“解释1”的基础上进行回答：仅考虑情况2，此时存在p1使得d(s,p) >=αd(p1,p)，其中α>1（当α=1时实际上就是SNG的构图策略），于是当s往p1遍历时，到p的距离会缩小至原来的1/β，(β>=α>1)，同理，再往下一个点遍历的时候，到p的距离会缩小至最开始的$1/{β^2}$ ，因此将从SNG的不确定的收敛速度提升至对数级收敛速度。
但这种建立出边集合的方式会导致图的平均度数更高

Vamana索引算法

Vamana以迭代的方式构建一个有向图G。图G的初始化使得每个顶点都有R个随机选择的出邻居（out-neighbors）。需要注意的是，虽然当R>logn时图的连通性良好，但随机连接并不能确保贪婪搜索（GreedySearch）算法收敛到理想的结果。

接下来，我们令s表示数据集P的中心点（medoid），它将作为搜索算法的起始节点。随后，算法按随机顺序遍历数据集P中的所有点p∈P，并在每一步中更新图，使其更适合GreedySearch(s,xp,1,L) 收敛至p。

具体而言，在对应点p的迭代中，Vamana首先在当前图G上运行GreedySearch(s,xp,1,L)，并将Vp设为该搜索过程所访问过的所有点的集合。然后，算法通过运行RobustPrune(p,Vp,α,R) 来确定p的新出邻居，从而更新G。接着，Vamana 为所有p′∈Nout(p) 添加反向边(p′,p)来进一步更新图G。这确保了搜索路径上访问过的顶点与p之间存在连接，从而保证更新后的图将更适合GreedySearch(s,xp,1,L)收敛至p。

然而，添加形式为(p′,p)的反向边可能会导致p′的度数超限（即违反度数限制）。因此，每当任何顶点p′的出度超过度数阈值R时，就会通过运行RobustPrune(p′,Nout(p′),α,R) 来修改图，其中Nout(p′)是p′当前的出邻居集合。

随着算法的推进，图的质量不断优化，使得贪婪搜索（GreedySearch）变得越来越快。我们的整体算法会对数据集进行两轮遍历（two passes）：第一轮遍历α=1，第二轮遍历则使用用户定义的 α≥1。我们观察到，进行第二轮遍历可以获得更好的图；而如果两轮遍历都使用用户定义的α，则会导致索引算法运行变慢，因为第一轮遍历会生成一个平均度数更高的图，从而耗费更长时间。

Vamana与HNSW及NSG的比较

从宏观层面来看，Vamana与两种非常流行的ANNS（近似最近邻搜索）算法 HNSW 和 NSG相当相似。这三种算法都会遍历数据集P，并利用GreedySearch(s,xp,1,L) 和RobustPrune(p,V,α,R) 的结果来确定点p的邻居。然而，这些算法之间存在一些重要的区别：
最关键的是，HNSW 和 NSG 都没有可调参数α，而是隐式地使用α=1。这是使 Vamana 能够在图度数和直径之间取得更好权衡的主要因素。
其次，在剪枝阶段，HNSW将候选集V设置为GreedySearch(s,p,1,L)输出的由L个候选点组成的最终结果集；而Vamana和NSG则将V设为GreedySearch(s,p,1,L) 过程中访问过的所有顶点集合。从直观上讲，这一特性有助于 Vamana 和 NSG 添加长程边；相比之下，由于 HNSW仅向邻近点添加局部边，它必须增加一个额外的步骤，即在数据集的嵌套采样序列上构建分层图
下一个差异在于初始图：NSG 将起始图设置为数据集的近似 K-最近邻图，这是一个耗费时间和内存的步骤；而 HNSW 和 Vamana 的初始化更为简单，前者从空图开始，而 Vamana 从随机图开始。我们观察到，相比于从空图开始，从随机图开始能生成质量更高的图。
最后，Vamana 对数据集进行两轮遍历，而 HNSW 和 NSG 都只进行一轮。这一做法源于我们的观察：第二轮遍历能够显著提升图的质量。

DiskANN：构建常驻SSD的索引

我们现在从两个部分介绍 DiskANN 的整体设计。在第一部分，我们将解释索引构建算法；在第二部分，我们将解释搜索算法。

DiskANN索引设计

宏观层面的思路很简单：在一个数据集P上运行 Vamana，并将生成的图存储在 SSD上。在搜索阶段，每当算法1需要获取某一点p的出邻居时，我们只需从SSD中读取该信息。然而，需要注意的是：仅仅是存储维度为100的十亿个点的向量数据，其容量就将远超一台工作站的内存（RAM）！ 这引发了两个问题：如果连向量数据都无法完整存放在内存中，我们该如何构建一个覆盖十亿个点的图？以及在搜索过程中（算法 1），我们该如何进行查询点与候选列表点之间的距离比较？

解决第一个问题的一种方法是：利用k-means等聚类技术将数据划分为多个较小的分片（shards） ，为每个分片构建独立的索引，并在搜索阶段仅将查询请求路由到少数几个分片。然而，这种方法会面临搜索延迟增加和吞吐量降低的问题，因为查询请求仍需通过多个分片进行路由处理。

我们的想法很简单：与其在查询阶段将请求路由到多个分片，不如将每个基础点分配给多个附近的中心，以获得重叠的簇 ？事实上，我们首先使用k-means 聚类将十亿点级别的数据集划分为k个簇（假设k=40），然后将每个基础点分配给与其最近的ℓ个中心（通常ℓ=2就足够了）。接着，我们为分配给每个簇的点构建 Vamana 索引（每个簇的点数现在仅约为Nℓ/k，因此可以在内存中构建索引），最后通过简单地将所有边取并集，将这些不同的图合并为一个单一的图。经验表明，不同簇的这种重叠特性为GreedySearch算法提供了足够的连通性，使其能够成功找到目标，即使查询点的最近邻实际上分散在多个分片中也是如此。我们想指出的是，早期已有研究曾通过合并多个较小的、重叠的索引来为大型数据集构建索引。然而，他们构建重叠簇的方法与我们不同，对这些不同技术进行更详细的对比研究还有待完成。

针对第二个问题，我们接下来的自然想法是：在主内存中为数据库中的每个点p∈P存储压缩向量$\bar{x}_p$ ，同时将图索引存储在 SSD 上。我们采用了一种名为乘积量化的流行压缩方案，它将数据点和查询点编码为简短代码 （例如，每个数据点仅占32字节），从而在运行算法1的查询阶段高效地计算出近似距离 d($\bar{x}_p$,xq)。需要说明的是，Vamana 在构建图索引时使用的是全精度坐标 ，因此即使我们在搜索阶段仅使用压缩数据，它也能有效地引导搜索流向图中的正确区域。

DiskANN索引布局

我们将所有数据点的压缩向量 存储在内存中，而将图索引与全精度向量 存储在 SSD 上。在磁盘中，对于每个点i，我们存储其全精度向量xi，紧接着存储其数量不超过R个的邻居标识。如果一个节点的度小于R，我们会用零进行填充，这样计算出任何点i对应数据在磁盘内的偏移量 (offset) 变成了一个简单的计算，且不需要在内存中存储偏移量表。我们将在下一节解释存储全精度坐标的必要性。

DiskANN束搜索

搜索给定查询xq邻居的一种自然方法是运行算法1，并根据需要从SSD获取邻域信息Nout(p∗)。可以使用压缩向量进行距离计算，从而引导系统选择最佳的顶点（及其邻域）从磁盘中读取。虽然这种方法行之有效，但它需要多次与 SSD 进行往返通信（每次往返耗时数百微秒），从而导致较高的延迟。为了在不显著增加计算量（距离计算）的情况下减少往返 SSD 获取数据的次数（避免顺序获取邻域），我们一次性（in one shot）获取L\V中少量（设为W，例如 4 或 8）最近邻点的邻域信息，并将L更新为原候选项及本步骤检索到的所有邻居中排名前L的候选点。需要注意的是，从 SSD 获取少量随机扇区的时间与获取单个扇区的时间几乎相同。我们将这种改进后的搜索算法称为束搜索 (BeamSearch) 。如果W=1，该搜索模式类似于普通的贪婪搜索。请注意，如果W太大（例如16或更多），则可能会浪费计算资源和 SSD 带宽。

虽然基于NAND闪存的SSD每秒可以提供超过50万次随机读取，但要实现最大读取吞吐量需要使所有的 I/O 请求队列达到饱和。然而，在队列积压的状态下以峰值吞吐量运行，会导致磁盘读取延迟超过一毫秒。因此，为了获得较低的搜索延迟，必须让SSD在较低的 负载因子下运行。我们发现，在较低的束宽 (beam widths)（例如 W=2,4,8）下运行，可以在延迟和吞吐量之间取得良好的平衡。在这种设置下，SSD 的负载因子处于 30%–40% 之间，运行搜索算法的每个线程约有 40%–50% 的查询处理时间花费在 I/O 等待上。

DiskANN缓存高频访问顶点

为了进一步减少每次查询的磁盘访问次数，我们将一部分顶点子集的相关数据缓存到DRAM（内存）中。缓存策略既可以基于已知的查询分布，也可以简单地缓存距离起点s在C=3或4跳范围内的所有顶点。由于索引图中距离起点为C的节点数量随C呈指数级增长，因此较大的C值会导致极大的内存占用。

DiskANN使用全精度向量进行隐式重排序

由于乘积量化（Product Quantization, PQ）是一种有损压缩方法，使用基于 PQ 的近似距离计算出的前k个候选点，与使用实际距离计算出的候选点之间存在偏差。为了弥补这一差距，我们利用了存储在磁盘上每个点邻域信息旁边的全精度坐标。事实上，在搜索过程中获取某个点的邻域信息时，我们也会同时抓取该点的全精度坐标，而不会产生额外的磁盘读取开销。这是因为，将4KB对齐的磁盘地址读入内存的成本并不比读取512B更高，且顶点的邻域（对于度数为128的图，长度为4×128字节）与全精度坐标可以存储在同一个磁盘扇区中。

因此，当束搜索（BeamSearch）加载搜索边界的邻域时，它也可以顺便缓存搜索过程中访问过的所有节点的全精度坐标，且无需对SSD进行额外读取。这使得我们能够基于全精度向量返回最终的前k个候选点。其它工作中也使用了获取并重排序存储在SSD上的全精度坐标的想法，但其算法是一次性（in one shot）获取所有待重排序的向量，这会导致瞬间产生数百次随机磁盘访问，进而对吞吐量和延迟产生负面影响。我们在后续提供了更详细的解释。在我们的方案中，获取全精度坐标本质上是“顺带”完成的，其开销已包含在扩展邻域的过程中。

评估

我们现在将 Vamana 与其他相关的近似最近邻搜索（ANNS）算法进行比较。首先，针对内存搜索，我们将我们的算法与 NSG和 HNSW进行对比，这两者在大多数公开基准数据集上均表现出了同类最佳的延迟与召回率权衡。接下来，针对大规模的十亿级点集，我们将 DiskANN 与基于压缩的技术（如FAISS和IVF-OADC+G+P）进行对比。
我们在所有实验中使用以下两台机器：

z840：一台裸机中端工作站，配备双路 Xeon E5-2620v4 处理器（共 16 核）、64GB DDR4 内存以及两块配置为 RAID-0 的三星 960 EVO 1TB SSD。
M64-32ms：一台虚拟机，配备双路 Xeon E7-8890v3 处理器（32 个虚拟 CPU）和 1792GB DDR3 内存，我们用它为十亿级点集构建一次性（one-shot）内存索引。

HNSW、NSG和Vamana的内存搜索性能对比

我们在三个常用的公开基准数据集上对比了 Vamana、HNSW 和 NSG：SIFT1M（128 维）和 GIST1M（960 维），这两者都是包含百万级图像描述符的点数据集；以及 DEEP1M（96 维），它是 DEEP1B（一个包含十亿个机器学习向量的集合）的百万量级随机采样样本。对于这三种算法，我们都进行了参数寻优，并选择了能实现最佳召回率与延迟权衡的近乎最优参数。所有 HNSW 索引的构建参数设为M=128，efC=512；而 Vamana 索引使用的参数为L=125，R=70，C=3000，α=2。对于 SIFT1M 和 GIST1M 上的 NSG，由于其表现优异，我们采用了其代码仓库中列出的参数；对于 DEEP1M，我们使用的参数为R=60，L=70，C=500。

此外，由于本项工作的重点在于基于SSD的搜索，我们没有专门为测试Vamana实现自己的内存搜索算法。相反，我们直接在Vamana生成的索引上使用了NSG仓库中经过优化的搜索算法实现。从图 3 中可以观察到一个清晰的趋势：在所有情况下，NSG和Vamana 的表现都优于 HNSW；而在 960 维的 GIST1M 数据集上，Vamana的表现则优于NSG和 HNSW。此外，在所有三个实验中，Vamana的索引构建时间也短于HNSW和NSG。例如，在z840 机器上对 DEEP1M 进行索引时，Vamana、HNSW 和 NSG的总索引构建时间分别为 149 秒、219 秒和 480 秒。根据这些实验，我们得出结论：在来自不同来源的百维和千维数据集上，Vamana 的性能表现与当前最先进的 ANNS 方法相当或更优。

HNSW、NSG和Vamana的跳数对比

相比于其他基于图的算法，Vamana更适合基于SSD的查询服务，因为在大型数据集上，要使搜索收敛，Vamana所需的跳数比HNSW和NSG少2到3倍。这里所说的“跳数”是指搜索关键路径上的磁盘读取轮数。在束搜索（BeamSearch）中，它对应于通过进行W次并行磁盘读取来扩展搜索前沿的次数。跳数非常重要，因为它直接影响搜索延迟。对于HNSW，我们假设除基础层以外的所有层级节点都缓存在DRAM中，因此只计算基础层图上的跳数。对于 NSG和Vamana索引，我们假设导航节点周围的前3个 BFS（广度优先搜索）层级可以缓存在 DRAM 中。

在图 2(c) 中，我们通过改变最大图度数，并对这三种算法均采用束宽度W=4 的束搜索算法，对比了达到 5-recall@5 为 98% 这一目标所需的跳数。我们注意到 HNSW 和 NSG 都表现出停滞趋势，而 Vamana 随着最大度数的增加，其跳数显著减少，这得益于它能够添加更多的长程边。因此我们推断，当α>1时，Vamana 比 HNSW 和 NSG 更好地利用了 SSD 提供的高容量特性。

十亿级数据集上的对比：一次性 Vamana 与合并式 Vamana

在接下来的实验中，我们将评估重点放在包含$10^9$个点的 ANN_SIFT1B bigann_数据集上，该数据集由128维uint8 类型的SIFT图像描述符组成。为了验证合并式 Vamana方案的有效性，我们使用 Vamana 构建了两个索引。

第一个是在完整的十亿级数据集上构建的单体索引（single index） ，参数设置为L=125,R=128,α=2。在 M64-32ms 机器上，此过程耗时约 2 天，峰值内存占用约为 1100GB，生成的索引平均度数为113.9。

第二个是合并索引（merged index） ，其构建步骤如下：

使用 k-means 聚类将数据集划分为k=40 个分片；
将数据集中的每个点分配给 ℓ=2个最近的分片中心；
为每个分片构建参数为L=125,R=64,α=2 的索引；
合并所有图的边集。

最终得到一个大小为 348GB、平均度数为 92.1 的索引。该索引在 z840 机器上构建，耗时约 5 天，且整个过程的内存使用量始终保持在 64GB 以下。由于数据集划分和图合并操作速度很快，且可以直接在磁盘上完成，因此整个构建过程消耗的主存不到 64GB。

我们在图 2(a) 中，通过使用 16 个线程运行搜索（每个查询仅在单个线程上处理），对比了两种配置在包含 10,000 个查询的 bigann 数据集上的 1-recall@1 与延迟表现。从该实验中，我们得出以下结论：

(a) 单体索引的性能优于合并索引 。合并索引为了到达相同的邻域需要遍历更多的链接，从而增加了搜索延迟。这可能是因为在合并索引中，每个节点的入边和出边被限制在总点数的约ℓ/k=5%范围内。

(b) 对于十亿量级的 k-ANN 索引和单节点服务，合并索引仍然是一个非常出色的选择，它轻松超越了现有的最先进方法。在达到相同目标召回率时，与单体索引相比，它仅多出不超过 20% 的额外延迟。另一方面，单体索引实现了新的最先进水平，在延迟不到 5 毫秒的情况下，1-recall@1 达到了 98.68%。

合并索引对于 DEEP1B 数据集也是一个很好的选择。图 2(b) 展示了在 z840 机器上，使用 k=40个分片和ℓ=2构建的合并式 DiskANN 索引在 DEEP1B 数据集上的召回率对比延迟曲线，搜索同样运行在 16 个线程上。

4.4 十亿级数据集上的对比：DiskANN 对比基于 IVF 的方法

我们最后的对比对象是FAISS和IVFOADC+G+P，这是最近在单节点上构建十亿级点集索引的两种方法。这两种方法都利用倒排索引和基于乘积量化的压缩方案，来构建具有低内存占用率的索引，从而能以高吞吐量提供查询服务并获得良好的 1-recall@100。我们仅将 DiskANN与IVFOADC+G+P 进行对比，因为先前文献证明了 IVFOADC+G+P 的召回率优于 FAISS，而且使用 FAISS 进行十亿级索引需要 GPU，而在某些平台上这些硬件可能并不可用。

IVFOADC+G+P 使用 HNSW 作为路由层来获取一小组聚类，并使用一种新颖的分组和剪枝策略对其进行进一步精细化。利用其开源代码，我们在 SIFT1B 基础集上构建了具有 16 字节和 32 字节 OPQ 码本的索引。图 2(a) 中的 IVFOADC+G+P-16 和 IVFOADC+G+P-32 曲线分别代表了这两种配置。IVFOADC+G+P-16 的 1-recall@1 停留在 37.04% 的水平，而规模更大的 IVFOADC+G+P-32 索引的 1-recall@1 达到了 62.74%。在与 IVFOADC+G+P-32 相同的内存占用下，DiskANN 的 1-recall@1 达到了完美的 100% 饱和值，同时在不到 3.5 毫秒的延迟下可提供 95% 以上的 1-recall@1。因此，DiskANN 在与基于压缩的方法保持相同内存占用的同时，能在相同延迟下实现显著更高的召回率。基于压缩的方法召回率较低，是由于坐标有损压缩导致精度损失，进而导致距离计算略有不准。

Zoom是一种类似于IVFOADC+G+P的基于压缩的方法，它通过压缩向量识别出K′>K个近似最近邻候选者，然后通过从磁盘获取全精度坐标进行重排序，以输出最终的K个候选者集合。然而，Zoom 存在两个缺陷：(a) 它通过并行的随机磁盘读取来获取所有K′个（即使 K=1，该数值也通常接近一百）全精度向量，这会影响延迟和吞吐量；(b) 它需要使用数十万个中心点进行昂贵的 k-means 聚类，以构建基于 HNSW 的路由层。

总结

我们提出并评估了一种名为 Vamana 的新型基于图的ANNS（近似最近邻搜索）索引算法，其索引在高召回率场景下的内存搜索性能与当前最先进的方法相当。此外，我们证明了在仅使用64GB主存的情况下，可以在十亿级数据集上构建高质量的驻留SSD索引 DiskANN。我们详细阐述并论证了相关的算法改进，这些改进使我们能够利用廉价的消费级SSD实现数毫秒级的查询延迟。通过将基于图的方法的高召回、低延迟特性与基于压缩的方法的高内存效率及可扩展性相结合，我们为十亿级数据集的索引和查询服务确立了新的技术标杆

【论文阅读;NeurIPS’19】DiskANN：单节点上快速、精准的十亿级数据点最近邻搜索

摘要

介绍