Fast Top-k Cosine Similarity Search Through Xor-friendly Binary Quantization On Gpus

Abstract

We explore the use of GPU for accelerating large scale nearest neighbor search and we propose a fast vector-quantization-based exhaustive nearest neighbor search algorithm that can achieve high accuracy without any indexing construction specifically designed for cosine similarity. This algorithm uses a novel XOR-friendly binary quantization method to encode floating-point numbers such that high-complexity multiplications can be optimized as low-complexity bitwise operations. Experiments show that, our quantization method takes short preprocessing time, and helps make the search speed of our exhaustive search method much more faster than that of popular approximate nearest neighbor algorithms when high accuracy is needed.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjian2020fast

Related papers

• Billion-scale Similarity Search With Gpus (2017)24.96
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Fast Cosine Similarity Search In Binary Space With Angular Multi-index Hashing (2016)8.60
• Polysemous Codes (2016)11.49
• Lossless Compression Of Vector Ids For Approximate Nearest Neighbor Search (2025)11.11
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82