2024/10/24 by Elias Jääsaari, Ville Hyvönen, Jääsaari, Elias +3 · 1 voice · 3 citations
Chemistry · Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Artificial intelligence #Best bin first #Chemistry #Combinatorics #Computer science #Cover tree #Face and Expression Recognition #Factorization #Mathematics #Matrix (chemical analysis) #Matrix decomposition #Nearest neighbor search #Pattern recognition (psychology) #Physics #Rank (graph theory) #Text and Document Classification Technologies #k-nearest neighbors algorithm
paper · pdf · doi:10.48550/arxiv.2410.18926
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2024/10/24 · openalex created_date 2024/11/13 · openalex updated_date 2026/07/28
Approximate nearest neighbor (ANN) search is a key component in many modern machine learning pipelines; recent use cases include retrieval-augmented generation (RAG) and vector databases. Clustering-based ANN algorithms, that use score computation methods based on product quantization (PQ), are often used in industrial-scale applications due to their scalability and suitability for distributed and disk-based implementations. However, they have slower query times than the leading graph-based ANN algorithms. In this work, we propose a new supervised score computation method based on the observation that inner product approximation is a multivariate (multi-output) regression problem that can be solved efficiently by reduced-rank regression. Our experiments show that on modern high-dimensional data sets, the proposed reduced-rank regression (RRR) method is superior to PQ in both query latency and memory usage. We also introduce LoRANN, a clustering-based ANN library that leverages the proposed score computation method. LoRANN is competitive with the leading graph-based algorithms and outperforms the state-of-the-art GPU ANN methods on high-dimensional data sets.