LSH_kNN_graph

[paper] [project]

The proposed method allows to create an approximate kNN graph in C++ for the diffusion application.
Then the retrieval is tested and the performance are the same or better than the ones obtained on the brute-force graph, but in less time (due to the reduction in the approximate kNN graph creation).

Datasets

The original dataset files are converted in binary through the application of a simple C++ script:

• Oxford5k
• Oxford105k

After downloading the dat files you need to create a folder called dataset and then put in the uncompressed version.
Remember to modify the path in the C++ files.

Installation

• Requirements:
  • G++ 5.4 or greater
  • openmp
  • cblas
• Build:
  g++ -o LSH_sparse LSH_sparse.cpp -lstdc++fs -std=c++14 -fopenmp -O2 -lcblas

Test

LSH kNN (δ = 6, L = 20, th = 5000, using global descriptors):
./LSH_sparse 6 20 oxford5k false 5000 0 ResNet50

multi LSH kNN graph (δ = 6, L = 20, th = 5000, 80% of multi-probe LSH, using global descriptors):
./LSH_sparse 6 20 oxford5k false 5000 80 ResNet50

For the diffusion application the python script implemented in the alzaman/paiss github is used.

Results

Oxford5k

Oxford105k

Reference

@article{magliani2019efficient,
  title={An Efficient Approximate kNN Graph Method for Diffusion on Image Retrieval},
  author={Magliani, Federico and McGuiness, Kevin and Mohedano, Eva and Prati, Andrea},
  journal={arXiv preprint arXiv:1904.08668},
  year={2019}
}
@inproceedings{dong2011efficient,
  title={Efficient k-nearest neighbor graph construction for generic similarity measures},
  author={Dong, Wei and Moses, Charikar and Li, Kai},
  booktitle={Proceedings of the 20th International Conference on World Wide Web},
  pages={577—586},
  year={2011},
  organization={ACM}
}
@inproceedings{sieranoja2018fast,
  title={Fast random pair divisive construction of kNN graph using generic distance measures},
  author={Sieranoja, Sami and Fr{\”a}nti, Pasi},
  booktitle={Proceedings of the 2018 International Conference on Big Data and Computing},
  pages={95—98},
  year={2018},
  organization={ACM}
}