eCite Digital Repository

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


Zhong, M and Liu, M and Bao, Z and Li, X and Qian, T, MVP index: towards efficient known-item search on large graphs, Database Systems for Advanced Applications, 22-25 April 2013, Wuhan, China, pp. 193-200. ISBN 978-3-642-37486-9 (2013) [Refereed Conference Paper]

Copyright Statement

Copyright 2013 Springer

DOI: doi:10.1007/978-3-642-37487-6_16


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.

Item Details

Item Type:Refereed Conference Paper
Keywords:graph search, database indexing
Research Division:Information and Computing Sciences
Research Group:Data management and data science
Research Field:Data management and data science not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Bao, Z (Dr Zhifeng Bao)
ID Code:92176
Year Published:2013
Deposited By:Information and Communication Technology
Deposited On:2014-06-09
Last Modified:2015-02-12

Repository Staff Only: item control page