QPAD: Quantile-Preserving Approximate Dimension Reduction for Nearest Neighbors Preservation in High-Dimensional Vector Search
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911281786650624 |
|---|---|
| author | Fu, Jiuzhou Zhao, Dongfang |
| author_facet | Fu, Jiuzhou Zhao, Dongfang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | QPAD: Quantile-Preserving Approximate Dimension Reduction for Nearest Neighbors Preservation in High-Dimensional Vector Search Fu, Jiuzhou Zhao, Dongfang Information Retrieval Databases 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. |
| title | QPAD: Quantile-Preserving Approximate Dimension Reduction for Nearest Neighbors Preservation in High-Dimensional Vector Search |
| topic | Information Retrieval Databases |
| url | https://arxiv.org/abs/2504.16335 |