LSH kNN graph for diffusion on image retrieval

Experimental results demonstrated the goodness of the diffusion mechanism for several computer vision tasks: image retrieval, semi-supervised and supervised learning, image classification. Diffusion requires the construction of a kNN graph in order to work. As predictable, the quality of the created graph influences the final results. Unfortunately, the larger the used dataset is, the more time the construction of the kNN graph takes, since the number of edges between nodes grows exponentially. A common and effective solution to deal with this problem is the brute-force method, but it requires a very long computation on large datasets. This paper proposes improvements on LSH kNN graph method that efficiently create an approximate kNN graph which is demonstrated to be faster than other state-of-the-art methods (18x faster than brute force on a dataset of more than 100k images) for content-based image retrieval, while obtaining also comparable performance in terms of accuracy. LSH kNN graph has been tested and compared with the state-of-the-art approaches for image retrieval on several public datasets, such as Oxford5k, ROxford5k, Paris6k, RParis6k and Oxford105k.