Efficient manifold ranking for image retrieval
- 24 July 2011
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 525-534
- https://doi.org/10.1145/2009916.2009988
Abstract
Manifold Ranking (MR), a graph-based ranking algorithm, has been widely applied in information retrieval and shown to have excellent performance and feasibility on a variety of data types. Particularly, it has been successfully applied to content-based image retrieval, because of its outstanding ability to discover underlying geometrical structure of the given image database. However, manifold ranking is computationally very expensive, both in graph construction and ranking computation stages, which significantly limits its applicability to very large data sets. In this paper, we extend the original manifold ranking algorithm and propose a new framework named Efficient Manifold Ranking (EMR). We aim to address the shortcomings of MR from two perspectives: scalable graph construction and efficient computation. Specifically, we build an anchor graph on the data set instead of the traditional k-nearest neighbor graph, and design a new form of adjacency matrix utilized to speed up the ranking computation. The experimental results on a real world image database demonstrate the effectiveness and efficiency of our proposed method. With a comparable performance to the original manifold ranking, our method significantly reduces the computational time, makes it a promising method to large scale real world retrieval problems.Keywords
This publication has 26 references indexed in Scilit:
- LIBSVMACM Transactions on Intelligent Systems and Technology, 2011
- Tag rankingPublished by Association for Computing Machinery (ACM) ,2009
- Image retrievalACM Computing Surveys, 2008
- A survey of content-based image retrieval with high-level semanticsPattern Recognition, 2006
- Fast monte-carlo algorithms for finding low-rank approximationsJournal of the ACM, 2004
- An efficient k-means clustering algorithm: analysis and implementationIeee Transactions On Pattern Analysis and Machine Intelligence, 2002
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Relevance feedback: a power tool for interactive content-based image retrievalIEEE Transactions on Circuits and Systems for Video Technology, 1998
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998