Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs
This work addresses the need for efficient and accurate similarity search in domains like information retrieval and machine learning, though it is incremental as it builds on existing quantization techniques.
The paper tackles the problem of accelerating large-scale nearest neighbor search for cosine similarity by proposing a fast exhaustive search algorithm using a novel XOR-friendly binary quantization method, which reduces high-complexity multiplications to low-complexity bitwise operations on GPUs, resulting in much faster search speeds than popular approximate methods while maintaining high accuracy.
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.