编者的总结

1. 本文在billion级别数据集上做的对比实验，结果不出意外，HNSW, Vamnna性能最稳定。值得注意的是，HCNNG在out-of-distribution数据集上适应更好，IVFPQ在range query上比其它方法性能高出一大截。
2. 一个现象是即使IVFPQ性能更高，距离计算次数却仍然会更多，作者没有解释原因。
3. 本文提了一个并行无锁化的插入式图构建框架，但会额外引入一些时间负担，但文中没有进一步解释。

编者的思考

1. 文章整体给出的insights不多，有些现象也只给了实验结论，没有进一步分析。
2. 文章用的机器非常强，少则96核，多则192核，对于查询，并行化没有任何竞争冲突；但对于构建这种有竞争冲突的，本文的实验可以提供一些参考。

Abstract

本文是在billion级别数据集做测评的文章，重点关注以下几个点：

1. 并行化能力
2. 构建时间
3. 伸缩性
4. 在查询性能方面，重点关注NDC，即每个Query平均距离计算次数
5. range query和out-of-distribution data

除此之外，本文还有两个贡献：

1. 四种图算法优化了在billion级别数据集下的性能。
2. 提供了一个泛化框架，让图索引的增量算法免于用锁

3 ANNS Algorithms

3.1 Graph-Based Algorithms

• 本文描述的统一插入算法的框架，把新插入点的NN search的访问集作为邻居集，这个在NSG和vamanna里面是这样的，在HNSW并不是。

  
  image.png

• 本文提出的并行无锁式插入算法如下。注意只有批量插入算法，实际上是一个并行构建算法。

• 要解决的问题就是加反向边的时候需要锁。

• 为了解决该问题，我们在为新插入点集找到邻居之后，统一收集这些邻居和这些邻居对应的新插入点，然后并行为这些邻居做更新。

image.png

除此之外，本文对search方面又做了两个优化：

• 一个是visit set的那个哈希表，为了加速查询，本文用了一个近似哈希表，这个哈希表永远不会碰撞，因为只要插入碰撞点，就把之前的点踢出去，这样可能会造成重新访问，不过实战问题不大。
• 另一个是搜的时候不会搜距离过远的邻居，具体来说就是超过倍当前BSF的距离，这样的Candidate直接跳过。

3.3 Algorithms Excluded

图算法分成了扁平图（Vamanna）和层次化图（HNSW）

4 Experimental Setup

实验有两台机器：

1. Msv2: four Intel® Xeon® Platinum 8280 Processors with 192 vCPUs 2TB 内存
2. ev5: two 3rd Generation Intel® Xeon® Platinum 8370C Processors with 96 vCPUs available to the user, and 672 GiB内存

所有核同时跑起来
算法参数如下：

image.png

5.1 Parallelism and Size Scaling

• 首先检验索引构建的并行度，这是本文提的新算法，批量并行构建；
• 随着线程数增加，如果总工作量保持不变，说明同步开销很小；
• 实线基本不变，说明同步开销很小；
• 48,96的位置有上升是因为总共就48核，96线程；
• 【不知道为什么HNSW在改良之后构建慢了这么多】

image.png

• 接下来我们看Scalability
• 构建时间是超线性的，可以归结于beam search的原因，即插入也是超线性的，即使是批量插入。
• 查询QPS降低不是线性的，不过这里是80% Recall10@10
• 【距离计算次数竟然没有同比增加，不知道这是怎么回事】

image.png

5.2 Full Billion-Scale Results

• range search Faiss的ivf-pq表现非常突出。

• HCNNG在out-of-distribution的数据集，Text2Image上表现不错；相比之下vamanna的性能在这个数据集上就差了一些。而且注意在这个数据集上所有方法的QPS都在下降，且幅度不小。

  
  image.png
  image.png

image.png

6 Conclusion and Future Work

作者基于实验结果提出了几个open problem:

1. HCNNG在out-of-distribution数据集上表现最优，Vamnna/HNSW在其他大数据集上表现最优，能否结合之？
2. 图方法在Range search上比FAISS-IVFPQ差很多，如何提升？