# EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2016.

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

- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [MobileRAG: A Fast, Memory-Efficient, and Energy-Efficient Method for On-Device RAG](https://mlsanity.com/paper/2507.01079/) (2025)
- [FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.11408/) (2022)
- [Hierarchical Semantic Retrieval with Cobweb](https://mlsanity.com/paper/2510.02539/) (2025)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios](https://mlsanity.com/paper/2505.09516/) (2025)
- [GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions](https://mlsanity.com/paper/2602.16719/) (2026)
- [Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms](https://mlsanity.com/paper/2102.06525/) (2021)
- [Distribution-Informed Adaptation for kNN Graph Construction](https://mlsanity.com/paper/2308.02442/) (2023)
- [GPU-accelerated Multi-relational Parallel Graph Retrieval for Web-scale Recommendations](https://mlsanity.com/paper/2502.11490/) (2025)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [PLASMA: A Layout-Aware Benchmark Reveals Memory Layout Matters for Graph-based ANNS on GPU](https://mlsanity.com/paper/2508.15436/) (2025)
- [FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2603.21710/) (2026)
- [Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning](https://mlsanity.com/paper/2609.36359/) (2026)

## Abstract (arXiv)

Approximate nearest neighbor (ANN) search is a fundamental problem in many areas of data mining, machine learning and computer vision. The performance of traditional hierarchical structure (tree) based methods decreases as the dimensionality of data grows, while hashing based methods usually lack efficiency in practice. Recently, the graph based methods have drawn considerable attention. The main idea is that a neighbor of a neighbor is also likely to be a neighbor, which we refer as NN-expansion. These methods construct a k-nearest neighbor (kNN) graph offline. And at online search stage, these methods find candidate neighbors of a query point in some way (eg, random selection), and then check the neighbors of these candidate neighbors for closer ones iteratively. Despite some promising results, there are mainly two problems with these approaches: 1) These approaches tend to converge to local optima. 2) Constructing a kNN graph is time consuming. We find that these two problems can be nicely solved when we provide a good initialization for NN-expansion. In this paper, we propose EFANNA, an extremely fast approximate nearest neighbor search algorithm based on kNN Graph. Efanna nicely combines the advantages of hierarchical structure based methods and nearest-neighbor-graph based methods. Extensive experiments have shown that EFANNA outperforms the state-of-art algorithms both on approximate nearest neighbor search and approximate nearest neighbor graph construction. To the best of our knowledge, EFANNA is the fastest algorithm so far both on approximate nearest neighbor graph construction and approximate nearest neighbor search. A library EFANNA based on this research is released on Github.