Scaling Manifold Ranking Based Image Retrieval
Abstract
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.
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 http://creativecommons.org/licenses/by-nc-nd/3.0/.Attached Files
Published - p341-fujiwara.pdf
Files
Name | Size | Download all |
---|---|---|
md5:a2100f42375c1edd3bccbfd7d4911375
|
1.4 MB | Preview Download |
Additional details
- Eprint ID
- 71466
- Resolver ID
- CaltechAUTHORS:20161025-145714402
- Created
-
2016-10-25Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field