Repository files navigation

[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).

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 calleddataset and then put in the uncompressed version.Remember to modify the path in the C++ files.

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

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 thealzaman/paiss github is used.

@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}}