Home

Awesome

NSG : Navigating Spread-out Graph For Approximate Nearest Neighbor Search

Cooperation

If you are interested in the research line of nearest neighbor search or application and looking for a cooperation please feel free to contect me via fc731097343@gmail.com

Table of Contents

<!--ts--> <!--te-->

Introduction

NSG is a graph-based approximate nearest neighbor search (ANNS) algorithm. It provides a flexible and efficient solution for the metric-free large-scale ANNS on dense real vectors. It implements the algorithm of our PVLDB paper - Fast Approximate Nearest Neighbor Search With The Navigating Spread-out Graphs. NSG has been intergrated into the search engine of Taobao (Alibaba Group) for billion scale ANNS in E-commerce scenario.

Performance

Datasets

Compared Algorithms

Graph-based ANNS algorithms:

Other popular ANNS algorithms:

Results

NSG achieved the best search performance among all the compared algorithms on all the four datasets. Among all the graph-based algorithms, NSG has the smallest index size and the best search performance.

NOTE: The performance was tested without parallelism (search one query at a time and no multi-threads)

SIFT1M-100NN-All-Algorithms

SIFT1M-100NN-All-Algorithms

SIFT1M-100NN-Graphs-Only

SIFT1M-100NN-Graphs-Only

GIST1M-100NN-All-Algorithms

GIST1M-100NN-All-Algorithms

GIST1M-100NN-Graphs-Only

GIST1M-100NN-Graphs-Only

RAND4M-100NN-All-Algorithms

RAND4M-100NN-All-Algorithms

RAND4M-100NN-Graphs-Only

RAND4M-100NN-Graphs-Only

GAUSS5M-100NN-All-Algorithms

GAUSS5M-100NN-All-Algorithms

GAUSS5M-100NN-Graphs-Only

GAUSS5M-100NN-Graphs-Only

DEEP1B-100NN

DEEP1B-100NN

Building Instruction

Prerequisites

IMPORTANT NOTE: this code uses AVX-256 intructions for fast distance computation, so your machine MUST support AVX-256 intructions, this can be checked using cat /proc/cpuinfo | grep avx2.

Compile On Ubuntu/Debian

  1. Install Dependencies:
$ sudo apt-get install g++ cmake libboost-dev libgoogle-perftools-dev
  1. Compile NSG:
$ git clone https://github.com/ZJULearning/nsg.git
$ cd nsg/
$ mkdir build/ && cd build/
$ cmake -DCMAKE_BUILD_TYPE=Release ..
$ make -j

(Optional) Docker Usage

  1. Build Docker Image
$ docker build -t nsg .
  1. Run and log into Docker container
$ docker run -it --name nsg nsg bash

You can modify the Dockerfile under the project as you need.

Usage

The main interfaces and classes have its respective test codes under directory tests/

Building NSG Index

To use NSG for ANNS, an NSG index must be built first. Here are the instructions for building NSG.

Step 1. Build kNN Graph

Firstly, we need to prepare a kNN graph.

We suggest you use our efanna_graph to build this kNN graph. But you can also use any alternatives you like, such as KGraph or faiss.

Step 2. Convert kNN Graph to NSG

Secondly, we will convert the kNN graph to our NSG index.

You can use our demo code to achieve this converstion as follows:

$ cd build/tests/
$ ./test_nsg_index DATA_PATH KNNG_PATH L R C NSG_PATH

Searching via NSG Index

Here are the instructions of how to use NSG index for searching.

You can use our demo code to perform kNN searching as follows:

$ cd build/tests/
$ ./test_nsg_optimized_search DATA_PATH QUERY_PATH NSG_PATH SEARCH_L SEARCH_K RESULT_PATH

There is another program in tests/ folder named test_nsg_search. The parameters of test_nsg_search are exactly same as test_nsg_optimized_search. test_nsg_search is slower than test_nsg_optimized_search but requires less memory. In the situations memory consumption is extremely important, one can use test_nsg_search instead of test_nsg_optimized_search.

NOTE: Only data-type int32 and float32 are supported for now.

HINT: The data_align() function we provided is essential for the correctness of our procedure, because we use SIMD instructions for acceleration of numerical computing such as AVX and SSE2. You should use it to ensure your data elements (feature) is aligned with 8 or 16 int or float. For example, if your features are of dimension 70, then it should be extend to dimension 72. And the last 2 dimension should be filled with 0 to ensure the correctness of the distance computing. And this is what data_align() does.

HINT: Please refer here for the desciption of fvecs/ivecs format.

Parameters used in Our Paper

NSG Building

We use the following parameters to get the index in Fig. 6 of our paper.

We use efanna_graph to build the kNN graph.

Step 1. Build kNN Graph

DatasetKLiterSR
SIFT1M2002001010100
GIST1M4004001215100
$ efanna_graph/tests/test_nndescent sift.fvecs sift_200nn.graph 200 200 10 10 100    # SIFT1M
$ efanna_graph/tests/test_nndescent gist.fvecs gist_400nn.graph 400 400 12 15 100    # GIST1M

Step 2. Convert kNN Graph to NSG

DatasetLRC
SIFT1M4050500
GIST1M6070500
$ nsg/build/tests/test_nsg_index sift.fvecs sift_200nn.graph 40 50 500 sift.nsg        # SIFT1M
$ nsg/build/tests/test_nsg_index gist.fvecs gist_400nn.graph 60 70 500 gist.nsg        # GIST1M

Pre-built kNN Graph and NSG Index

Here we also provide our pre-built kNN graph and NSG index files used in our papar's experiments.

Performance on Taobao's E-commerce Data

Environments:

Single Thread Test:

Distributed Search Test:

Reference

Reference to cite when you use NSG in a research paper:

@article{FuNSG17,
  author    = {Cong Fu and Chao Xiang and Changxu Wang and Deng Cai},
  title     = {Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphs},
  journal   = {{PVLDB}},
  volume    = {12},
  number    = {5},
  pages     = {461 - 474},
  year      = {2019},
  url       = {http://www.vldb.org/pvldb/vol12/p461-fu.pdf},
  doi       = {10.14778/3303753.3303754}
}

TODO

License

NSG is MIT-licensed.