A Caltech Library Service

Scaling Manifold Ranking Based Image Retrieval

Fujiwara, Yasuhiro and Irie, Go and Kuroyama, Shari and Onizuka, Makoto (2014) Scaling Manifold Ranking Based Image Retrieval. Proceedings of the VLDB Endowment, 8 (4). pp. 341-352. ISSN 2150-8097.

[img] PDF - Published Version
Creative Commons Attribution Non-commercial No Derivatives.


Use this Persistent URL to link to this item:


Manifold Ranking is a graph-based ranking algorithm being successfully applied to retrieve images from multimedia databases. Given a query image, Manifold Ranking computes the ranking scores of images in the database by exploiting 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 matrix to compute ranking scores and so needs O(n^3) time, where n is the number of images. Manifold Ranking, unfortunately, 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 reduce the time complexity of Mogul to O(n) from O(n^3) 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2014 VLDB Endowment. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. To view a copy of this license, visit
Issue or Number:4
Record Number:CaltechAUTHORS:20161025-145714402
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71466
Deposited By: Kristin Buxton
Deposited On:25 Oct 2016 22:24
Last Modified:03 Oct 2019 16:07

Repository Staff Only: item control page