Concurrent image query using local random walk with restart on large scale graphs

Abstract

Efficient image query is a fundamental challenge in many large scale multimedia applications, especially when handling many queries concurrently. In this paper, we proposed a novel approach called graph local random walk for high performance concurrent image query. Specifically, we organize the massive images set into a large scale graph using graph database, according to the similarity between images. A heuristic method is utilized to map each query image to some vertex in the graph, followed by a local search to refine the query results using an alternative of local random walk on graph. The local random walk process is essentially a weighted partial traversal in the local subgraphs for finding a better match of the query images. We organize the graph of the image set in a parallelization amenable approach, so that a set of partial graph traversal for local random walk can be performed concurrently, taking the advantage of the multithreading capability of processors. We implemented the proposed method in state-of-the-art multicore platforms. The experimental result shows that the graph local random walk based approach outperforms baseline methods in terms of both throughput and scalability.