Fast Manifold-Ranking for Content-Based Image Retrieval

Manifold-Ranking (MR) has been successfully used in content-based image retrieval (CBIR) in recent years. However, the straightforward implementations of MR do not scale for large image database, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem, which exploit two important properties shared by many real graphs, i.e. linear correlations and block-wise community-like structure. We exploit the linearity by using low-rank matrix approximation and the community structure by graph partitioning, which is followed by the Sherman-Morrison lemma for matrix inversion. Experimental results on the Corel image demonstrate that our proposed methods achieve significant savings over the straightforward implementations, which show the effectiveness of our approach.