Dimensionality-reduction Techniques For Approximate Nearest Neighbor Search: A Survey And Evaluation

Abstract

Approximate Nearest Neighbor Search (ANNS) on high-dimensional vectors has become a fundamental and essential component in various machine learning tasks. Recently, with the rapid development of deep learning models and the applications of Large Language Models (LLMs), the dimensionality of the vectors keeps growing in order to accommodate a richer semantic representation. This poses a major challenge to the ANNS solutions since distance calculation cost in ANNS grows linearly with the dimensionality of vectors. To overcome this challenge, dimensionality-reduction techniques can be leveraged to accelerate the distance calculation in the search process. In this paper, we investigate six dimensionality-reduction techniques that have the potential to improve ANNS solutions, including classical algorithms such as PCA and vector quantization, as well as algorithms based on deep learning approaches. We further describe two frameworks to apply these techniques in the ANNS workflow, and theore

Stats

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

Related papers

• Lorann: Low-rank Matrix Factorization For Approximate Nearest Neighbor Search (2024)2.26
• Exploring The Meaningfulness Of Nearest Neighbor Search In High-dimensional Space (2024)2.26
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• Parlayann: Scalable And Deterministic Parallel Graph-based Approximate Nearest Neighbor Search Algorithms (2023)10.35
• SAQ: Pushing The Limits Of Vector Quantization Through Code Adjustment And Dimension Segmentation (2025)0.00
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19
• Lucene For Approximate Nearest-neighbors Search On Arbitrary Dense Vectors (2019)0.00
• Subspace Collision: An Efficient And Accurate Framework For High-dimensional Approximate Nearest Neighbor Search (2024)7.16