Unsupervised manifold learning using Reciprocal kNN Graphs in image re-ranking and rank aggregation tasks

•Presentation of an unsupervised manifold learning algorithm using Reciprocal kNN Graphs•Presentation of the Reciprocal kNN Graph ReRanking for improving the effectiveness of CBIR systems•Description of how Reciprocal kNN Graph algorithm can be used for rank aggregation tasks•Discussion about the computational complexity and the convergence of proposed algorithm•Experimental evaluation considering different datasets, descriptors, and baselines

In this paper, we present an unsupervised distance learning approach for improving the effectiveness of image retrieval tasks. We propose a Reciprocal kNN Graph algorithm that considers the relationships among ranked lists in the context of a k-reciprocal neighborhood. The similarity is propagated among neighbors considering the geometry of the dataset manifold. The proposed method can be used both for re-ranking and rank aggregation tasks. Unlike traditional diffusion process methods, which require matrix multiplication operations, our algorithm takes only a subset of ranked lists as input, presenting linear complexity in terms of computational and storage requirements. We conducted a large evaluation protocol involving shape, color, and texture descriptors, various datasets, and comparisons with other post-processing approaches. The re-ranking and rank aggregation algorithms yield better results in terms of effectiveness performance than various state-of-the-art algorithms recently proposed in the literature, achieving bull's eye and MAP scores of 100% on the well-known MPEG-7 shape dataset.