MVP index: towards efficient known-item search on large graphs

This paper is motivated by the lack of study on the diversity of user information needs in the scenario of graph search, which offers the prospect of significant improvements on search.We report our investigation on this issue, and then exploit the knowledge to optimize a commonly-used type of graph search: known-item search which only wants the answer trees of a familiar and compact pattern. To address the problem, we propose a novel MVP (Matched Vertex Pruning) index, which captures the query-independent local connectivity information in the graph, to reduce the search space with heuristics by pruning matched vertices that will not participate in the answer trees with heights less than a threshold. Moreover, our optimization approach is independent of search algorithm, and requires the minimal index access times. Our experimental results show that our approach can generally reduce the number of matched vertices to 1%-10%, thereby effectively improving the efficiency of the known-item search.