一句话：提出 Juno，结合稀疏感知算法与 GPU 光线追踪核心映射，加速高维近似最近邻搜索。
近似最近邻（ANN）搜索广泛用于推荐系统和向量数据库，但基于乘积量化的先进方法存在大量不必要的成对距离计算与累加，导致效率不高。本文提出端到端 ANN 搜索系统 Juno：设计稀疏性与局部性感知的搜索算法，减少冗余距离计算；并给出高效硬件映射，利用现代 GPU 的光线追踪核心，并在张量核心上流水线执行该算法。在 1 到 1 亿搜索点的四个数据集上评估，搜索吞吐提升 2.2×–8.5×；仅算法增强在不使用 RT 核心加速的硬件上也能取得最高 2.6× 提升。
Approximate nearest neighbor (ANN) search is a widely applied technique in modern intelligent applications, such as recommendation systems and vector databases. Therefore, efficient and high-throughput execution of ANN search has become increasingly important. In this paper, we first characterize the state-of-the-art product quantization-based method of ANN search and identify a significant source of inefficiency in the form of unnecessary pairwise distance calculations and accumulations. To improve efficiency, we propose Juno, an end-to-end ANN search system that adopts a carefully designed sparsity- and locality-aware search algorithm. We also present an efficient hardware mapping that utilizes ray tracing cores in modern GPUs with pipelined execution on tensor cores to execute our sparsity-aware ANN search algorithm. Our evaluations on four datasets from 1 to 100 million search points demonstrate 2.2×-8.5× improvements in search throughput. Moreover, our algorithmic enhancements alone achieve a maximal 2.6× improvement on the hardware without the acceleration of the RT core.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{LiuNLFGCLG024,
title = {JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and Ray-Tracing Core Mapping},
author = {Zihan Liu and Wentao Ni and Jingwen Leng and Yu Feng and Cong Guo and Quan Chen and Chao Li and Minyi Guo and Yuhao Zhu},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3620665.3640360}
}