EFANNA: an Extremely Fast Approximate Nearest Neighbor search Algorithm framework based on kNN graph

EFANNA is a flexible and efficient library for approximate nearest neighbor search (ANN search) on large scale data. It implements the algorithms of our paper EFANNA : Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph.
EFANNA provides fast solutions on both approximate nearest neighbor graph construction and ANN search problems. EFANNA is also flexible to adopt all kinds of hierarchical structure for initialization, such as random projection tree, hierarchical clustering tree, multi-table hashing and so on.

What's new

• The paper updated significantly. Dec 6, 2016
• Algorithm improved and AVX instructions supported. Nov 30, 2016
• Parallelism with OpenMP. Sep 26, 2016

Benchmark data set

• SIFT1M and GIST1M

ANN search performance

The performance was tested without parallelism.

Compared Algorithms:

• kGraph
• flann
• IEH : Fast and accurate hashing via iterative nearest neighbors expansion
• GNNS : Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

kNN Graph Construction Performance

The performance was tested without parallelism.

Compared Algorithms:

• Kgraph (same with NN-descent)
• NN-expansion (same with GNNS)
• SGraph : Scalable k-NN graph construction for visual descriptors
• FastKNN : Fast kNN Graph Construction with Locality Sensitive Hashing
• LargeVis : Visualizing Large-scale and High-dimensional Data

How To Complie

Go to the root directory of EFANNA and make.

cd efanna/
make

How To Use

EFANNA uses a composite index to carry out ANN search, which includes an approximate kNN graph and a number of tree structures. They can be built by this library as a whole or seperately.

You may build the kNN graph seperately for other use, like other graph based machine learning algorithms.

Below are some demos.

• kNN graph building :

    cd efanna/samples/   
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 8 30 25 10 10   
  

Meaning of the parameters(from left to right):

sift_base.fvecs -- database points  
sift.graph -- graph built by EFANNA   

8 -- number of trees used to build the graph (larger is more accurate but slower)   
8 -- conquer-to-depeth(smaller is more accurate but slower)   
8 -- number of iterations to build the graph 
 
30 -- L (larger is more accurate but slower, no smaller than K)  
25 -- check (larger is more accurate but slower, no smaller than K)  
10 -- K, for KNN graph   
10 -- S (larger is more accurate but slower)

• tree building :

    cd efanna/samples/
    ./efanna_index_buildtrees sift_base.fvecs sift.trees 32
  

  Meaning of the parameters(from left to right):

  sift_base.fvecs -- database points
  sift.trees -- struncated KD-trees built by EFANNA
  32 -- number of trees to build

• index building at one time:

    cd efanna/samples/
    ./efanna_index_buildall sift_base.fvecs sift.graph sift.trees 32 8 8 200 200 100 10 8
  

  Meaning of the parameters(from left to right)

  sift_base.fvecs -- database points
  sift.trees -- struncated KD-trees built by EFANNA
  sift.graph -- approximate KNN graph built by EFANNA 32 -- number of trees in total for building index
  8 -- conquer-to-depth
  8 -- iteration number
  200 -- L (larger is more accurate but slower, no smaller than K)
  200 -- check (larger is more accurate but slower, no smaller than K)
  100 -- K, for KNN graph 10 -- S (larger is more accurate but slower)
  8 -- 8 out of 32 trees are used for building graph

• ANN search

    cd efanna/samples/
    ./efanna_search sift_base.fvecs sift.trees sift.graph sift_query.fvecs sift.results 16 4 1200 200 10
  

  Meaning of the parameters(from left to right):

  sift_base.fvecs -- database points
  sift.trees -- prebuilt struncated KD-trees used for search
  sift.graph -- prebuilt kNN graph
  sift_query -- sift query points
  sift.results -- path to save ANN search results of given query
  16 -- number of trees to use (no greater than the number of prebuilt trees)
  4 -- number of epoches
  1200 -- pool size factor (larger is more accurate but slower, usually 6~10 times larger than extend factor)
  200 -- extend factor (larger is more accurate but slower)
  10 -- required number of returned neighbors (i.e. k of k-NN)

• Evaluation

    cd efanna/samples/
    ./evaluate sift.results sift_groundtruth.ivecs 10
  

  Meaning of the parameters(from left to right):

  sift.results -- search results file
  sift_groundtruth.ivecs -- ground truth file
  10 -- evaluate the 10NN accuracy (the only first 10 points returned by the algorithm are examined, how many points are among the true 10 nearest neighbors of the query)

See our paper or user manual for more details about the parameters and interfaces.

Output format

The file format of approximate kNN graph and ANN search results are the same.
Suppose the database has N points, and numbered from 0 to N-1. You want to build an approximate kNN graph. The graph can be regarded as a N * k Matrix. The saved kNN graph binary file saves the matrix by row. The first 4 bytes of each row saves the int value of k, next 4 bytes saves the value of M and next 4 bytes saves the float value of the norm of the point. Then it follows k*4 bytes, saving the indices of the k nearest neighbors of respective point. The N rows are saved continuously without seperating characters.

Similarly, suppose the query data has n points, numbered 0 to n-1. You want EFANNA to return k nearest neighbors for each query. The result file will save n rows like the graph file. It saves the returned indices row by row. Each row starts with 4 bytes recording value of k, and follows k*4 bytes recording neighbors' indices.

Input of EFANNA

Because there is no unified format for input data, users may need to write input function to read your own data. You may imitate the input function in our sample code (sample/efanna_efanna_index_buildgraph.cc) to load the data into our matrix.

To use SIMD instruction optimization, you should pay attention to the data alignment problem of SSE / AVX instruction.

Compare with EFANNA without parallelism and SSE/AVX instructions

To disable the parallelism, there is no need to modify the code. Simply

    export OMP_NUM_THREADS=1

before you run the code. Then the code will only use one thread. This is a very convenient way to control the number of threads used.

To disable SSE/AVX instructions, you need to modify samples/xxxx.cc, find the line

    FIndex<float> index(dataset, new L2DistanceAVX<float>(), efanna::KDTreeUbIndexParams(true, trees ,mlevel ,epochs,checkK,L, kNN, trees, S));

Change L2DistanceAVX to L2Distance and build the project. Now the SSE/AVX instructions are disabled. If you want to try SSE instead of AVX, try L2DistanceSSE

Parameters to get the Fig. 4/5 (10-NN approximate graph construction) in our paper

SIFT1M:

    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 0 20 10 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 1 20 10 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 2 20 10 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 3 20 10 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 5 20 10 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 6 20 20 10 10
    ./efanna_index_buildgraph sift_base.fvecs sift.graph 8 8 6 20 30 10 10

GIST1M:

    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 2 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 3 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 4 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 5 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 6 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 7 30 30 10 10
    ./efanna_index_buildgraph gist_base.fvecs gist.graph 8 8 10 30 40 10 10

Acknowledgment

Our code framework imitates Flann to make it scalable, and the implemnetation of NN-descent is taken from Kgraph. They proposed the NN-descent algorithm. Many thanks to them for inspiration.

What to do

• Add more initial algorithm choice