Billion-scale Similarity Search With Gpus

Abstract

Similarity search finds application in specialized 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, prior approaches are bottlenecked by algorithms that expose less parallelism, such as k-min selection, or make poor use of the memory hierarchy. We propose a design for k-selection that operates at up to 55% of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5x faster than prior GPU state of the art. We apply it in different similarity search scenarios, by proposing optimized design for 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 enables the construction of a high accuracy k-NN graph on 95 mil

Stats

• citations2127
• S2 citations—
• github stars0
• HF likes0
• heat score24.96
• arxiv keyjohnson2017billion

Related papers

• Fast Top-k Cosine Similarity Search Through Xor-friendly Binary Quantization On Gpus (2020)0.00
• CAGRA: Highly Parallel Graph Construction And Approximate Nearest Neighbor Search For Gpus (2023)12.17
• GGNN: Graph-based GPU Nearest Neighbor Search (2019)13.39
• A Generic Inverted Index Framework For Similarity Search On The GPU - Technical Report (2016)0.00
• Billion-scale Similarity Search Using A Hybrid Indexing Approach With Advanced Filtering (2025)4.52
• All-in-one Graph-based Indexing For Hybrid Search On Gpus (2025)0.00
• FLASH: Randomized Algorithms Accelerated Over CPU-GPU For Ultra-high Dimensional Similarity Search (2017)9.23
• GPU Accelerated Cascade Hashing Image Matching For Large Scale 3D Reconstruction (2018)0.00