# High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations

arXiv: https://arxiv.org/abs/2303.09855 · HTML: https://mlsanity.com/paper/2303.09855/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2023.

## Built on by (most cited first, 26 of 26)

- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [RAGO: Systematic Performance Optimization for Retrieval-Augmented Generation Serving](https://mlsanity.com/paper/2503.14649/) (2025)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Panorama: Fast-Track Nearest Neighbors](https://mlsanity.com/paper/2510.00566/) (2025)
- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)
- [Bang for the Buck: Vector Search on Cloud CPUs](https://mlsanity.com/paper/2505.07621/) (2025)
- [UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture](https://mlsanity.com/paper/2410.23805/) (2024)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [Trading Vector Data in Vector Databases](https://mlsanity.com/paper/2511.07139/) (2025)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)
- [Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach](https://mlsanity.com/paper/2603.06660/) (2026)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)
- [NasZip: Software and Hardware Co-Design to Accelerate Approximate Nearest Neighbor Search with DIMM-Based Near-Data Processing](https://mlsanity.com/paper/2605.21952/) (2026)
- [ANN Search: Recall What Matters](https://mlsanity.com/paper/2606.04522/) (2026)
- [HNSW with Accuracy Guarantees Using Graph Spanners](https://mlsanity.com/paper/2607.02338/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)

## Abstract (arXiv)

Approximate K nearest neighbor (AKNN) search is a fundamental and challenging problem. We observe that in high-dimensional space, the time consumption of nearly all AKNN algorithms is dominated by that of the distance comparison operations (DCOs). For each operation, it scans full dimensions of an object and thus, runs in linear time wrt the dimensionality. To speed it up, we propose a randomized algorithm named ADSampling which runs in logarithmic time wrt to the dimensionality for the majority of DCOs and succeeds with high probability. In addition, based on ADSampling we develop one general and two algorithm-specific techniques as plugins to enhance existing AKNN algorithms. Both theoretical and empirical studies confirm that: (1) our techniques introduce nearly no accuracy loss and (2) they consistently improve the efficiency.