Tree-based Search Graph for Approximate Nearest Neighbor Search

TBSG: Tree-based Search Graph for Approximate Nearest Neighbor Search.

TBSG is a graph-based algorithm for ANNS based on Cover Tree, which is also an approximation of Monotonic Search Network (MSNET). TBSG is very efficient with high precision.

Benchmark datasets

Datasets | No. of base | dimension | No. of query | download link
Sift | 1,000,000 | 128 | 10,000 | (http://corpus-texmex.irisa.fr/)
Gist | 1,000,000 | 300 | 1,000 | (http://corpus-texmex.irisa.fr/)
Glove | 1,183,514 | 100 | 10,000 | (http://downloads.zjulearning.org.cn/data/glove-100.tar.gz)
Crawl | 1,989,995 | 300 | 10,000 | (http://commoncrawl.org/)

How to use TBSG

1) compile

• Prerequisite : openmp, cmake, eigen3

$ cd /path/to/project  
$ cmake . && make  

2) build an approximate kNNG

We use efanna_graph to build the kNNG.

3) create a TBSG index

$ cd /path/to/project/  
$ ./TBSG_index data_path M S MP nnfile save_path  

data_path is the path of base data.
M is the maximum of size of neighbors.
S is the candidate set size to build TBSG.
MP is the minimum of min_prob.
nnfile is the file of k nearest neighbor graph.
save_path is the path to save the index.

4) search with TBSG index

$ cd /path/to/project/
$ ./TBSG_search data_path query_path groundtruth_path save_path step

data_path is the path of base data.
query_path is the path of query data.
groundtruth is the path of groundtruth data.
save_path is the path to save the index.
step is the step size to expand the search pool.

Parameters used for four datasets

parameters for building kNNG

parameters for building index