# Effective and General Distance Computation for Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2024.

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

- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [Connect the Dots: Knowledge Graph-Guided Crawler Attack on Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2601.15678/) (2026)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [SINDI: An Efficient Index for Sparse Vector Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2509.08395/) (2025)
- [Panorama: Fast-Track Nearest Neighbors](https://mlsanity.com/paper/2510.00566/) (2025)
- [The Hybrid Multimodal Graph Index (HMGI): A Comprehensive Framework for Integrated Relational and Vector Search](https://mlsanity.com/paper/2510.10123/) (2025)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)

## Abstract (arXiv)

Approximate K Nearest Neighbor (AKNN) search in high-dimensional spaces is a critical yet challenging problem. In AKNN search, distance computation is the core task that dominates the runtime. Existing approaches typically use approximate distances to improve computational efficiency, often at the cost of reduced search accuracy. To address this issue, the state-of-the-art method, ADSampling, employs random projections to estimate approximate distances and introduces an additional distance correction process to mitigate accuracy loss. However, ADSampling has limitations in both effectiveness and generality, primarily due to its reliance on random projections for distance approximation and correction. To address the effectiveness limitations of ADSampling, we leverage data distribution to improve distance computation via orthogonal projection. Furthermore, to overcome the generality limitations of ADSampling, we adopt a data-driven approach to distance correction, decoupling the correction process from the distance approximation process. Extensive experiments demonstrate the superiority and effectiveness of our method. In particular, compared to ADSampling, our method achieves a speedup of 1.6 to 2.1 times on real-world datasets while providing higher accuracy.