Billion-Scale Similarity Search with GPUs
Billion-Scale Similarity Search with GPUs
复制标题
DOI：
10.1109/tbdata.2019.2921572
复制
发表时间：
2021-07-01
影响因子：
7.2
通讯作者：
Jegou, Herve
中科院分区：
文献类型：
--
作者：
Johnson, Jeff;Douze, Matthijs;Jegou, Herve
相似性搜索在处理图像或视频等复杂数据的数据库系统中得到应用，这些数据通常由高维特征表示，并需要特定的索引结构。本文解决了更好地利用GPU来完成这一任务的问题。虽然GPU擅长数据并行任务，如距离计算，但该领域的现有方法受到并行度较低的算法(如k-min选择)的瓶颈，或者不能很好地利用内存层次结构。我们提出了一种新的k-选择算法设计。通过对基于乘积量化的暴力搜索、近似搜索和压缩域搜索进行优化，将其应用于不同的相似搜索场景。在所有这些设置中，我们的表现远远超过了最先进的水平。我们的实现以高达55%的理论峰值性能运行，实现了比以前的GPU技术状态快8.5倍的最近邻实现。它能够在35分钟内从Y(FCC)100M数据集中构建9500万张图像的高精度k-NN图，并在4个Maxwell Titan X GPU上在不到12小时内构建连接10亿个矢量的图。为了便于比较和重现性，我们将我们的方法开源。
Similarity search finds application in database systems handling complex data such as images or videos, which are typically represented by high-dimensional features and require specific indexing structures. This paper tackles the problem of better utilizing GPUs for this task. While GPUs excel at data parallel tasks such as distance computation, prior approaches in this domain are bottlenecked by algorithms that expose less parallelism, such as k-min selection, or make poor use of the memory hierarchy. We propose a novel design for k-selection. We apply it in different similarity search scenarios, by optimizing brute-force, approximate and compressed-domain search based on product quantization. In all these setups, we outperform the state of the art by large margins. Our implementation operates at up to 55 percent of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5 x faster than prior GPU state of the art. It enables the construction of a high accuracy k-NN graph on 95 million images from the Y(FCC)100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs. We have open-sourced our approach for the sake of comparison and reproducibility.