Optimized-Product-Quantization-and-KNN-Search-based-on-KNN-Graph

An implementation of K Nearest Neighbors Search based on KNN-Graph and Optimized Product Quantization

Tools

Eigen 3
Intel MKL
Opencv 3.4.5

Datasets

SIFT-1M & GIST-1M :

Download
Then put all .fvecs and .ivecs files under './dataset'.

Self-made binary files for KNN Search with OPQ :

Download from BaiduPan with key 6raq
Then put them all under './dataset/256bits_100iter_8bits'
Also, you could choose to encode you results (codebook, centroids, lookuptable, matrix R) of Optimized Product Quantization into such kind of files using encoder.m. The source Matlab code of Optimized Product Quantization can be found in here

100NN-Graph

Build a 100NN-Graph from given dataset and encode it into binary file and make sure the binary file has the same structure as .ivecs. Then place it under ./dataset

K Nearest Neighbors Search based on KNN-Graph

How to run it

details are provided in the demo main.cpp

Performance

QPS-Precision on SIFT-1M and GIST-1M with 100NN-Graph

QPS-Precision on SIFT-1M with XNN-Graph

and its memory usage

Optimized Product Quantization

How to run it

Details are provided in the demo main.cpp

Performance

Distortion with different code length on SIFT-1M