PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Cong Fu, Deng Cai

arXiv:1609.07228v3cs.CV

TL;DR

ANN search becomes costly or less effective for dense, high-dimensional data, while graph-based methods face initialization and kNN-graph construction challenges. EFANNA combines hierarchical structures with graph refinement and reports significant improvements in both ANN search and approximate graph construction. Its performance boost does not increase linearly with index width, indicating an upper bound as the index grows.

  • Problem

    Dense and high-dimensional ANN search remains challenging, and graph-based approaches face local-optimum behavior and expensive kNN-graph construction.

  • Method

    EFANNA combines multiple hierarchical structures for initialization with an approximate kNN graph refined through NN-expansion or NN-descent.

  • Results

    EFANNA significantly outperforms previous algorithms in both approximate kNN graph construction and ANN search, including more than 300× speed-up over brute-force construction to reach 95% accuracy.

  • Takeaways & Limitations

    EFANNA provides a fast framework for approximate nearest-neighbor search and approximate kNN graph construction across different scenarios.

  • Takeaways & Limitations

    Performance gains do not increase linearly with EFANNA index width, suggesting an upper bound as tree or graph size grows.

Abstract

from arXiv · show

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 \emph{a neighbor of a neighbor is also likely to be a neighbor}, which we refer as \emph{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 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 $k$NN 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.

1 INTRODUCTION

EFANNA addresses the limitations of existing ANN methods by combining hierarchical initialization with graph-based NN-expansion. It also targets the costly construction of approximate kNN graphs and reports strong empirical performance.

  • Exact nearest-neighbor search costs O(N) for dense data, motivating approximate search on large datasets.
  • Tree-based methods degrade in high dimensions, while hashing methods may require examining many buckets to maintain recall.
  • Graph-based methods use NN-expansion but can converge to local optima and require costly kNN-graph construction.
  • EFANNA combines multiple randomized hierarchical structures with an approximate kNN graph to improve candidate initialization and refinement.
  • EFANNA searches hierarchical structures for candidates, then refines them through NN-expansion on the approximate graph.
  • EFANNA is reported to outperform state-of-the-art ANN methods and build approximate kNN graphs hundreds of times faster than brute force.

2 RELATED WORK

ANN methods include tree-, hashing-, and graph-based approaches, each addressing high-dimensional neighbor search through different indexing strategies. EFANNA’s related work emphasizes NN-expansion and the importance of efficient graph initialization and construction.

  • Tree-based ANN methods become inefficient as dimensionality grows, motivating newer hierarchical structures such as randomized KD-trees and Kmeans trees.
  • Hashing methods partition feature space into binary-coded regions, but neighboring points may fall into different buckets and require nearby-bucket checks.
  • Graph-based methods use NN-expansion, iteratively examining neighbors of candidate points after constructing an offline kNN graph.
  • Efficient approximate kNN graph construction remains important because exact methods are still inefficient for large databases.
  • Prior divide-and-conquer approaches initialize graphs by repeatedly partitioning data, brute-force searching subsets, and merging overlapping subgraphs.
  • The reviewed algorithmic framework combines randomized tree construction with candidate expansion and iterative neighbor checking.

3 EFANNA ALGORITHMS FOR ANN SEARCH

EFANNA combines multiple hierarchical structures with an approximate kNN graph: trees initialize candidates, while graph expansion searches and refines neighbors. Its divide-and-conquer graph construction limits comparisons by selecting nearby leaf nodes before refinement.

  • EFANNA overview: EFANNA combines multiple hierarchical structures for initialization with an approximate kNN graph for NN-expansion.
  • ANN search: Randomized truncated KD-trees provide initial query candidates, after which graph neighbors are iteratively expanded and retained by distance.
  • ANN search: Search uses expansion factor E, candidate pool size P, and iteration number I; the experiments fix I = 4 while E and P trade speed against accuracy.
  • Hierarchical index: The truncated KD-tree stores K = 10 points per leaf instead of one, making tree construction faster than traditional randomized KD-trees.
  • Graph construction: Approximate graph construction first uses tree-based overlapping divisions and then applies NN-descent to refine the initial graph.
  • Graph construction: At each divide-and-conquer level, EFANNA considers only the closest possible leaf in a sibling subtree, reducing computation while preserving accuracy.

4 EXPERIMENTS

The experiments evaluate EFANNA on the SIFT1M and GIST1M real-world datasets using controlled C++ implementations. The reported setup specifies compiler, disabled optimizations, hardware, and dataset sources.

  • The experiments evaluate EFANNA on two real-world datasets: SIFT1M and GIST1M.
  • Both datasets are publicly downloadable, and their detailed characteristics are listed in Table 1.
  • The C++ code uses g++4.9 with only O3 optimization, while SSE instructions and parallelism are disabled.
  • SIFT1M experiments use an i7-3770K CPU with 16G memory, whereas GIST1M experiments use an i7-4790K CPU with 32G memory.

4.2 Experiments on ANN Search

The experiments compare ANN methods using average recall and time-recall curves on SIFT1M and GIST1M, with graph methods evaluated using a ground-truth 10-NN graph. EFANNA achieves the strongest reported search performance while trading additional index structure for speed.

  • Evaluation protocol: Average recall measures the fraction of returned points that belong to the query’s true k nearest neighbors, averaged across queries.The evaluation varies the requested neighborhood size, including 1-NN and 100-NN.
  • Compared methods: The comparison includes brute-force search, FLANN, GNNS, and kGraph, with graph-based methods using a pre-built ground-truth 10-NN graph.The figures report time-recall curves for the compared algorithms on SIFT1M and GIST1M.
  • Results: EFANNA significantly outperforms the other methods across both datasets and all tested cases.At 95% recall, it is about 100x faster than brute-force on SIFT1M and about 10x faster on GIST1M.
  • Results: For larger neighborhoods, graph-based methods outperform FLANN’s KD-tree, while EFANNA’s advantage is attributed to its truncated KD-tree initialization.The shared framework isolates initialization: GNNS uses random selection, IEH uses hashing, and EFANNA uses a truncated KD-tree.
  • Results: EFANNA uses an index size slightly larger than IEH, but graph-based methods offer a better search-performance and index-size trade-off than FLANN’s KD-tree.The paper notes that EFANNA can reduce index size by using fewer trees while maintaining high performance.

4.3 Experiment on Approximate kNN Graph Construction

This section evaluates approximate 10-NN graph construction using accuracy–time curves on SIFT1M and GIST1M. EFANNA achieves the strongest reported construction speed while using randomized truncated KD-tree initialization.

  • Evaluation Protocol: Graph construction is evaluated by average neighbor-set accuracy versus construction time for returned 10-NN graphs.For each point, the returned neighbors are compared with the ground-truth set, and graph accuracy averages these per-point accuracies.
  • Comparison Algorithms: The experiments compare brute-force, SGraph, FastKNN, NN-expansion, and NN-descent for approximate kNN graph construction.SGraph and FastKNN use different initial-graph strategies, while NN-descent refines a randomly initialized graph iteratively.
  • Results: EFANNA achieves more than 300× speed-up over brute-force construction at 95% accuracy.On GIST1M, brute-force construction takes about a week without parallelism, whereas EFANNA reduces the time to less than an hour.
  • Results: EFANNA exceeds 300× speed-up on both SIFT1M and GIST1M, while SGraph previously reported 100× on SIFT1M and 50× on GIST1M.The cited comparison notes that the original FastKNN timing omitted hashing time, affecting comparability.
  • Results: EFANNA differs from NN-descent mainly through initialization: it uses randomized truncated KD-trees, whereas NN-descent uses random initialization.The reported advantage is larger on SIFT1M than GIST1M, where higher dimensionality may make KD-tree initialization less effective.

4.4 EFANNA with Approximate kNN Graphs

This section tests EFANNA when its search graph is approximate rather than ground truth. Search remains strong with substantially imperfect graphs, and lower-accuracy graphs can reduce indexing cost while retaining favorable comparisons.

  • Experiment: EFANNA is evaluated on approximate kNN graphs with varying accuracy on SIFT1M and GIST1M.The experiments use 10-NN graphs and report search results for the two datasets.
  • Results: A 60%-accurate 10-NN graph still makes EFANNA significantly better than Flann-kdtree on SIFT1M.The SIFT1M figure evaluates 10,000 queries with both methods using 16 trees.
  • Results: With a 60%-accurate graph, EFANNA has indexing time similar to Flann-kdtree, a smaller index, and significantly better ANN search performance.The comparison combines indexing-time and index-size results with the search evaluation.
  • Results: A 57%-accurate 10-NN graph still makes EFANNA significantly better than Flann-kdtree on GIST1M.The GIST1M experiment evaluates 1,000 queries and uses 16 trees for both methods.
  • Why Approximate Graphs Work: In SIFT1M, a 60%-accurate EFANNA graph contains 98.9% true 100-nearest neighbors despite only 60% true 10-nearest neighbors.The remaining graph neighbors are therefore near neighbors rather than random points from the dataset.

4.5 EFANNA with Different Number of Trees

This section examines how the number of truncated KD-trees affects EFANNA’s search and index size. Fewer trees reduce the index while lowering performance, but EFANNA remains competitive with only four trees.

  • Experiment: The experiment varies the number of truncated KD-trees while using the 10-NN ground-truth graph.The trees are used for EFANNA’s search initialization, and the study compares search performance and index size.
  • Results: Reducing the number of trees decreases ANN search performance for both EFANNA and Flann.The comparison uses SIFT1M and GIST1M results against IEH-ITQ and FLANN.
  • Results: With only 4 trees, EFANNA remains significantly better than IEH-ITQ, especially on GIST1M.At this setting, EFANNA’s index size is also smaller than IEH-ITQ’s.
  • Trade-off: The number of trees provides a trade-off between EFANNA’s index size and ANN search performance.The section presents this flexibility as a way to adjust the index according to the desired resource–performance balance.

4.6 EFANNA with Different Number of k in kNN Graph

This section studies the effect of increasing the kNN graph width from 10 to 40 neighbors. Wider graphs improve ANN search more effectively than adding trees at equal extra memory cost, although gains are not linear.

  • Experiment: EFANNA’s graph width is the k value in its N × k kNN-graph matrix, and the experiment compares 10-NN, 20-NN, and 40-NN graphs.Search performance is evaluated on SIFT1M and GIST1M, with corresponding index sizes reported.
  • Results: EFANNA index size grows gradually as graph width increases from 10-NN to 40-NN.The associated figures evaluate approximate nearest neighbor search on SIFT1M and GIST1M.
  • Results: ANN search performance increases as EFANNA’s graph width grows.The reported comparison covers the 10-NN, 20-NN, and 40-NN configurations.
  • Trade-off: At equal extra memory cost, widening the graph improves EFANNA more than adding trees.The section compares the graph-width and tree-count experiments to reach this resource-allocation conclusion.
  • Limitation: Performance gains from increasing graph width are not linear and may have an upper bound as index size grows.The same limitation applies to increasing either graph width or tree count.

4.7 ANN Search Comparison with Same Index Size

With nearly equal index sizes, EFANNA and other graph-based methods were compared against flann’s KD-tree on SIFT1M and GIST1M. Graph methods delivered substantially faster search, while EFANNA’s advantage depended on dataset, recall, and graph width.

  • About 265 MB of index space was used for each algorithm, with EFANNA configured using four trees and a 40NN graph.The comparison included EFANNA, IEH-ITQ, GNNS, and flann’s KD-tree on SIFT1M and GIST1M.
  • Over 20x speedup over flann’s KD-tree was achieved by graph-based methods on both datasets with the same index size.EFANNA was about 30x faster than flann’s KD-tree.
  • EFANNA’s performance gain over IEH-ITQ and GNNS became smaller as graph width increased, reducing the impact of initialization quality.
  • At 95% recall on SIFT1M, the three graph methods performed almost the same, while GNNS was better for 100NN.At low recall, EFANNA and IEH-ITQ retained a small advantage over GNNS.
  • On GIST1M, EFANNA retained an advantage over IEH-ITQ and GNNS, indicating that initialization behavior differed across datasets.The passage characterizes GIST1M as harder for approximate nearest-neighbor search and reports GNNS outperforming IEH-ITQ.

5 THE EFANNA LIBRARY

The EFANNA work was released as an open-source library, with its code available on GitHub.

  • EFANNA was released as an open-source library.
  • The released library is based on the work described in the paper.
  • The code can be accessed through GitHub.

6 CONCLUSION

EFANNA targets fast approximate nearest-neighbor search and approximate kNN graph construction. It combines hierarchical initialization and graph-based construction, and experiments report strong performance across scenarios.

  • EFANNA provides a fast solution for approximate nearest-neighbor search and approximate kNN graph construction.
  • For ANN search, EFANNA uses hierarchical structures to provide better initialization for NN-expansion.
  • For graph construction, EFANNA builds an initial graph with divide-and-conquer and refines it using NN-descent.
  • Extensive experiments report that EFANNA significantly outperforms previous algorithms in approximate kNN graph construction and ANN search.
  • EFANNA shows flexibility across different scenarios.
Loading 1609.07228v3…