BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU

近似最近邻搜索（ANNS）是信息检索、模式识别、数据挖掘、图像处理等算法中常用的子程序。最近的研究表明，基于图的ANNS算法在大型数据集上比文献中提出的其他方法实际上更有效率。由于数据的增长和维度性增强，需要设计可扩展的ANNS技术。为此，先前的研究已经探索了在GPU上并行化基于图的ANNS，利用其高计算能力和能源效率。目前最先进的基于GPU的ANNS算法要么需要索引图和数据都完全驻留在GPU内存中，要么将数据分成小的独立分片，每个分片都可以适应GPU内存，并在GPU上执行搜索。虽然第一种方法由于GPU内存的有限而无法处理大型数据集，但后一种方法在大型数据集上的性能较差，因为在低带宽PCIe总线上存在高数据流量。在本文中，我们介绍了BANG，这是一种首创的基于GPU的ANNS方法，可在无法完全适应GPU内存的十亿级数据集上高效运行。BANG通过在GPU上利用压缩数据进行距离计算，同时保持CPU上的图表。BANG包含高度优化的GPU内核，并分阶段在GPU和CPU上同时运行，利用它们的体系结构特性。我们使用单个NVIDIA Ampere A100 GPU对十个流行的ANN基准数据集进行了BANG评估。在大多数情况下，BANG的性能优于最先进的方法。值得注意的是，在十亿级数据集上，我们比竞争对手快得多，在高召回率为0.9的情况下，实现的吞吐量比竞争方法高40倍至200倍。

该论文旨在解决大规模数据集下GPU-based ANNS算法内存限制和低带宽PCIe总线的性能问题。

BANG算法利用GPU上的压缩数据执行距离计算，同时将图形保留在CPU上，通过GPU和CPU的并发阶段来提高性能。

BANG算法在十个流行的ANN基准数据集上进行了评估，取得了比现有算法更好的性能。在处理十亿级别的数据集时，BANG的吞吐量比竞争方法高40倍至200倍，同时保持高召回率0.9。

近期的相关研究包括基于GPU的ANNS算法和大规模数据集处理技术，如《Efficient GPU-based Approximate Nearest Neighbor Search》和《Large-Scale Similarity Search with GPUs》。