QPAD: Quantile-Preserving Approximate Dimension Reduction for Nearest Neighbors Preservation in High-Dimensional Vector Search

2025/04/23 by Jinsheng Fu, Fu, Jiuzhou, Dongfang Zhao +1
Computer Science · #Advanced Image and Video Retrieval Techniques #Databases (cs.DB) #FOS: Computer and information sciences #Face and Expression Recognition #Information Retrieval (cs.IR) #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.2504.16335

openalex publication_date 2025/04/23 · openalex created_date 2025/10/11 · openalex updated_date 2026/08/04

Abstract

High-dimensional vector embeddings are widely used in retrieval systems, but they often suffer from noise, the curse of dimensionality, and slow runtime. However, dimensionality reduction (DR) is rarely applied due to its tendency to distort the nearest-neighbor (NN) structure that is critical for search. Existing DR techniques such as PCA and UMAP optimize global or manifold-preserving criteria, rather than retrieval-specific objectives. We present QPAD -- Quantile-Preserving Approximate Dimension Reduction, an unsupervised DR method that explicitly preserves approximate NN relations by maximizing the margin between k-NNs and non-k-NNs under a soft orthogonality constraint. We analyze its complexity and favorable properties. This design enables QPAD to retain ANN-relevant geometry without supervision or changes to the original embedding model, while supporting scalability for large-scale vector search and being indexable for ANN search. Experiments across five domains show that QPAD consistently outperforms eleven standard DR methods in preserving neighborhood structure, enabling more accurate search in reduced dimensions.

Citations

• Survey of Vector Database Management Systems
• Survey of vector database management systems
• A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
• SEANet: A Multi-modal Speech Enhancement Network
• ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms
• Approximate Nearest Neighbor Search in High Dimensions
• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
• Non-negative Matrix Factorization: Robust Extraction of Extended Structures
• Feature Agglomeration Networks for Single Stage Face Detection
• Practical Hash Functions for Similarity Estimation and Dimensionality Reduction
• Contrastive Principal Component Analysis
• Billion-scale similarity search with GPUs
• FastText.zip: Compressing text classification models
• Enriching Word Vectors with Subword Information
• Enriching Word Vectors with Subword Information
• Bag of Tricks for Efficient Text Classification
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• Nonlinear Dimensionality Reduction by Locally Linear Embedding

Related

• RAE: A Neural Network Dimensionality Reduction Method for Nearest Neighbors Preservation in Vector Search
• Dimensionality-Reduction Techniques for Approximate Nearest Neighbor Search: A Survey and Evaluation
• SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation
• Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search
• Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrieval