Scaling Manifold Ranking Based Image Retrieval

Manifold Ranking is a graph-based ranking algorithm be-ing successfully applied to retrieve images from multimedia databases. Given a query image, Manifold Ranking com-putes the ranking scores of images in the database by ex-ploiting the relationships among them expressed in the form of a graph. Since Manifold Ranking effectively utilizes the global structure of the graph, it is significantly better at finding intuitive results compared with current approaches. Fundamentally, Manifold Ranking requires an inverse ma-trix to compute ranking scores and so needs O(n3) time, where n is the number of images. Manifold Ranking, un-fortunately, does not scale to support databases with large numbers of images. Our solution, Mogul, is based on two ideas: (1) It efficiently computes ranking scores by sparse matrices, and (2) It skips unnecessary score computations by estimating upper bounding scores. These two ideas re-duce the time complexity of Mogul to O(n) from O(n3) of the inverse matrix approach. Experiments show that Mogul is much faster and gives significantly better retrieval quality than a state-of-the-art approximation approach. 1