CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs

解决问题：本篇论文的目的是提出一种新的并行计算硬件基础下的近似最近邻搜索算法，旨在解决数据量增大导致精确最近邻搜索计算成本过高的问题。该问题并不是一个新问题，但是该论文的解决方案是新的。

关键思路：该论文的关键思路是提出一种基于并行计算硬件的近似最近邻搜索算法，利用现代硬件的高性能能力，实现了显著的效率提升。该方法在构建近邻图方面比当前CPU和GPU方法更快，同时在大批量和小批量搜索中均具有更高的吞吐量和兼容的准确性。相比当前领域的研究状况，该论文的思路具有新意。

其他亮点：该论文的实验使用了多个数据集，并且提供了开源代码。该算法的效率在构建近邻图和搜索方面均有显著提升，值得进一步研究和应用。

相关研究：近期的相关研究还包括：

  • "Efficient and Effective Approximate Nearest Neighbor Search on High-Dimensional Data: A Survey of Techniques and Applications" by Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li from Carnegie Mellon University
  • "Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph" by Ting Chen, Yizhou Sun, Yuanqi Chen, and Jiawei Han from University of Illinois at Urbana-Champaign
  • "ANNGP: Approximate Nearest Neighbor with Gaussian Process" by Shuai Li, Jia Wu, and Xiaoyu Zhang from University of Chinese Academy of Sciences and University of Electronic Science and Technology of China.

论文摘要：近似最近邻搜索（ANNS）在数据挖掘和人工智能等各个领域中都扮演着至关重要的角色，从信息检索、计算机视觉到自然语言处理和推荐系统。近年来，数据量急剧增长，穷举精确最近邻搜索的计算成本经常是不可承受的，因此需要采用近似技术。基于图的方法的平衡性能和召回率最近在ANNS算法中受到了重视，然而，尽管广泛使用大规模并行和通用计算，但只有少数研究探讨了利用GPU和多核处理器的能力。为了弥补这一差距，我们引入了一种新的基于并行计算硬件的近邻图和搜索算法。通过利用现代硬件的高性能能力，我们的方法实现了显著的效率提高。特别是，在构建近邻图方面，我们的方法CAGRA比HNSW快2.2~27倍，后者是CPU SOTA实现之一。在90%到95%召回率范围内的大批量查询吞吐量方面，我们的方法比HNSW快33~77倍，并且比GPU的SOTA实现快3.8~8.8倍。对于单个查询，我们的方法在95%召回率时比HNSW快3.4~53倍。

内容中包含的图片若涉及版权问题，请及时与我们联系删除