标题：磁盘近似最近邻搜索：单节点上对10亿个点级别的快速准确最近邻搜索

编者的总结

1. 本文的核心想法，是怎么把图索引放到SSD上，还能减少IO。要想减少IO，就要缩短直径和查询条数，因此引入了因子，虽然增加了度数，但是减少了直径，因此缩减了IO，这在实验中得以证实。
2. 第二个点是设计了Vamanna图，去除了NSG中以KNNG作为基础图再剪枝的思路，初始只用一个随机图再补充边进行筛选，提升了构建效率。
3. 为了能够在内存中构建索引，采取了k-means分shard，然后利用overlap来merge成图的策略，从结果上来看，效果和完整图差的不多，是一个成功的尝试。
4. 将距离起点最近3跳的点缓存，这些点每次query必然用到，是一个成功的缓存策略。
5. 总的来说，解决了基于图的KNN算法中的可扩展性问题。

编者的思考

1. 构建时间还是太长了，一台性能强劲的服务器，要几天的时间。内存使用可以算是合理的，和同等级的DB领域的方法相比，这个时间还是太长了。
2. 不能精确查询，近似查询也没有保证，是AI领域KNN方法的通病。
3. 一个思考，如果图不存原始数据集，只存邻居节点信息，图索引就会小的多，每个节点要存储的信息也要少得多（512B），基于一个图分区算法，让每个节点的附近尽量存储其邻居节点，每次读取时就大概率能多读未来一跳或几跳，利用图的本地性，会不会进一步减少IO呢？

Abstract

目前基于图的索引都是基于内存的，因此对数据集大小有限制。本文提出的基于SSD的磁盘索引，可以搜索SIFT1B大数据集。
相比于同样内存开销的FAISS，IVFOADC+G+P等方法，召回率更高；
相比于同样准确率的HNSW,NSG等方法，能服务更大的数据集。

1 Introduction

在内存数据集搜索上：

• KD-Tree搜索速度快，但是维度超过20就变得非常慢；
• LSH没有关注数据分布，实际效果不如基于图的方法，最新的LSH(2015STOC)关注了数据分布，但没有验证扩展性；
• 截止目前（2019），搜索速度和召回最好的是基于图的方法。

在外存数据集搜索上：

• 第一种是翻转索引+数据压缩的方式，首先将数据分区，每次只搜索和query接近的几个区，数据点在内存以乘积量化（PQ）的方式压缩存储，精度损失较大。主要方法就是FAISS，IVFOADC+G+P等。主要问题就在于放到大数据集上召回太低了，实际效果到了没法用的程度。
• 第二种方法就是分shard。把基于图的数据分成若干shard，每个shard分别做索引，查询的时候先分别查，然后将结果聚合。按论文单位淘宝的设计，一个单节点机器只能索引6千万左右的数据。

本文把索引放到了SSD上，目标是减少SSD随机访问次数到几十次，减少SSD round-trip（指对SSD的一次request，可能包含多个读）次数到5次左右。

2 The Vamana Graph Construction Algorithm

首先给出一些背景知识。

2.1 Relative Neighborhood Graphs and the GreedySearch algorithm

• 贪婪搜索：基于图的搜索通常是贪婪搜索，从一个给定的起点s开始，每次迈向距离q(query)最近的邻居。
• SNG：这种贪婪搜索的理论基础是这样的搜索路径必须能逐步收敛距离，如何能满足这样的收敛性呢？只需要构建一个特殊的图，对于图中一个节点p，构造一个候选人集合S，初始化为除了p的所有点；首先在S中选择距离p最近的点，然后驱逐S中所有满足的点p'，重复这个过程。这样的图就能满足收敛性。这个图称为SNG(sparse neighborhood graph)，或者RNG(Relative Neighborhood Graph)。
• 代价分析：由于每个点找邻居都要算O(n)次距离，所以构建图就要的复杂度，这个无论如何也接受不了，所以大家一般都在找SNG图的近似方案，只要能近似收敛性也就可以了。
• 近似方案：NSG，HNSW就是SNG的近似方案。但是，这些近似算法在控制图的直径和密度方面几乎没有什么灵活性。

2.2 The Robust Pruning Procedure

• 直径问题：SNG图的直径可能非常的长。考虑在一维情况下图的所有点排成一条线，此时每个点就两个邻居就是它左右的两位，满足SNG图要求，图直径是n。这种超长直径将导致贪婪搜索时许多的磁盘顺序读来找邻居。
• 解决方案：才被驱逐，补一个乘法因子，此时能保证收敛是对数速度的。
• 代价分析：构建图还是的复杂度，必须大幅缩小候选集S，才能减少构建索引的时间。

2.3 The Vamana Indexing Algorithm

本文提的这个新的索引算法和NSG的思路非常像：

• 初始化：图中每个点R个随机出边邻居，s是数据集的中心；
• 迭代：以随机顺序迭代数据集中的每个点p：
  1. 从s开始对p进行贪婪搜索，记录路径上遇到过的点集V；
  2. 以点集V作为候选集，重新抉择p的R个邻居，和这新的R个邻居双向连接；
  3. 如果邻居的出度超了R，那就以其当前的出度邻居为候选集，重新选R个邻居作为出度。
• 迭代做两次，一次，一次。
  • 作者的理由是，两次使得图的效果更好，第一次效率更高。
    
    image.png

2.4 Comparison of Vamana with HNSW and NSG

虽然三种方法都是在用贪婪搜索为图赋边，但仍有许多不同：

1. HNSW和NSG本质上都是用，因此无法控制度数和直径的trade-off。
2. HNSW用贪婪搜索的结果集作为候选集，Vamana和NSG用的是路径节点集。因此HNSW都是局部的连接，需要通过层次化补充长范围的边。【编者注：这一点上没多大区别，路径节点集最后也是选的最近的一批；NSG和Vamana的L(efCons)可以比较小，收敛的快一点，返回的visit set数量多质量差；HNSW的efCons一般设置大一些，收敛慢一些，质量好一些。NSG可以用小的L是因为有Kgraph打底，Vamana这里用小L反而不合适了】
3. NSG初始化图为KNN图，费时费力；HNSW用空图，Vamana用随机图，实验证明随机图质量稍好一些【编者注：后来Vamana在代码中也用空图了】。
4. HNSW和NSG都是一轮迭代，Vamana是两轮，主要发现是两轮有助于质量提升。【编者注：这里的两轮不同地方也有不同实现，有的是从搜索开始，把第一轮当base用，有的是第一轮预留多一点邻居，然后第二轮只剪枝】

3 DiskANN: Constructing SSD-Resident Indices

这一节我们正式讨论如何基于磁盘做Graph-based索引。

3.1 The DiskANN Index Design

构建索引有两个问题。

• 第一个问题：不可能把全部数据都load到内存里来，图如何构建？

  • 一个解决方案是用k-means将图分成k个shards，每个shard分别建图，查询时路由到各个shard进行搜索，然后对结果进行归并。问题在于分别路由延迟高且吞吐低。为了避免分别路由，还是要做一整个图。
  • 为了解决这个问题，我们采取了“分治”技术。首先还是做k-means分shard，但是，每个聚类中心被分配(一般取2)个最近的cluster。然后，对每个聚类中心下辖的个cluster拉到内存里构建Vamana图。k个聚类中心都建好图之后，把它们merge起来，形成一张大图。
    • 注意到各个聚类中心的子图之间是有重叠的，正是这种重叠提供了大图足够的连接度。
    • 这种图领域里的“分治”技术以前也有人提出过，具体的重叠技术却有所不同，需要有人来做评估。

• 第二个问题：再做贪婪搜索时要让query和数据集中的点算距离，不可能把每个点的向量精确放在内存里，又不可能一个一个取，怎么算距离？

  • 贪婪搜索时的距离用近似距离代替。这个近似距离用乘积量化（PQ）的方式来完成。向量的PQ表示全放在内存。
    • 注意构建时用的可是原始向量，但搜索时就只用PQ过的向量来近似。

3.2 DiskANN Index Layout

向量的PQ表示全放在内存，图放在SSD，原始数据放SSD。
再SSD上，对于每个节点，首先放原始序列，然后是它的R个邻居的id，不足R个的用0补位使得偏移量是确定的。

3.3 DiskANN Beam Search

贪婪搜索算法中，我们每次取优先级队列中的最小距离的点作为访问，然后取其邻居进入优先级队列，重复此过程。
考虑到从SSD中一次取多个扇区和1个扇区的时间几乎差不多，因此我们可以从优先级队列中一次多出队几个，一起去取邻居，这样节省IO时间。称为集束搜索（Beam Search）。

• 对于SSD来说，吞吐量和单请求延迟是一个trade-off。要想吞吐量最大，必须要积压请求队列，此时单请求延迟接近1ms。为了保证请求延迟较低，不能让SSD负载太高。

集束宽度（每次出队个数）大约在2,4,8左右，可以保证SSD负载在30%-40%，此时算法的IO时间在40%-50%。

3.4 DiskANN Caching Frequently Visited Vertices

从s开始，3到4跳的节点全部缓存至内存，以减少IO访问。

3.5 DiskANN Implicit Re-Ranking Using Full-Precision Vectors

之前说过，在SSD上，每个节点首先存原始数据，然后是邻居。默认参数下，邻居的字节数512B，磁盘一块4KB，完全可以把原始数据一起读上来。用真实数据做搜索，则不必用PQ损失精度。

4 Evaluation

实验用了两台超强的机器：

image.png

4.1 Comparison of HNSW, NSG and Vamana for In-Memory Search Performance

• 1M数据集，三种方法查询速度、质量差不多，都很极致。索引构建时间上：Vamana(129s)，HNSW（219s），NSG（480s），普遍都较慢。

  
  
  image.png

4.2 Comparison of HNSW, NSG and Vamana for Number of Hops

• Vamana跳数更少，收敛更快，这取决于变大能有效降低图的直径，而跳数直接影响查询速度。
  
  image.png

4.3 Comparison on Billion-Scale Datasets: One-Shot Vamana vs Merged Vamana

1B大数据集。

• 集中式构建图索引，用上面提到的M64-32ms超强机器，建索引用了2天，内存最高使用高达1.1T。
• merged图索引构建，用上面的z840强机器，建了5天，内存使用不到64GB，生成索引大小也有348GB。

• 查询质量上，这种图式的索引，要比乘积量化系列的方法要好一大截，这是可以想象到的。另外R128作为全图索引，比merged要好也是肯定的。

  
  
  image.png
  
  
  image.png