Beyond diffusion process: Neighbor set similarity for fast re-ranking

Measuring the similarity between two instances reliably, shape or image, is a challenging problem in shape and image retrieval. In this paper, a simple yet effective method called Neighbor Set Similarity (NSS) is proposed, which is superior to both traditional pairwise similarity and diffusion process. NSS makes full use of contextual information to capture the geometry of the underlying manifold, and obtains a more precise measure than the original pairwise similarity. Moreover, based on NSS, we propose a powerful fusion process to utilize the complementarity of different descriptors to further enhance the retrieval performance. The experimental results on MPEG-7 shape dataset, N-S image dataset and ORL face dataset demonstrate the effectiveness of the proposed method. In addition, the time complexity of NSS is much lower than diffusion process, which suggests that NSS is more suitable for large scale image retrieval than diffusion process.