EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph

Abstract

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 (\(k\)NN) 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 \(k\)NN graph is time consuming. We find that these tw

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfu2016efanna

Related papers

• Approximate K-nn Graph Construction: A Generic Online Approach (2018)11.08
• Approximate Nearest Neighbour Search On Dynamic Datasets: An Investigation (2024)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• FINGER: Fast Inference For Graph-based Approximate Nearest Neighbor Search (2022)10.74
• Relative Nn-descent: A Fast Index Construction For Graph-based Approximate Nearest Neighbor Search (2023)8.09
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00