MVP index: towards efficient known-item search on large graphs
conference contribution
posted on 2023-05-23, 08:57authored byZhong, M, Liu, M, Bao, Z, Li, X, Qian, T
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.
History
Publication title
Database Systems for Advanced Applications
Volume
7825
Editors
W Meng, L Feng, S Bressan, W Winiwarter, W Song
Pagination
193-200
ISBN
978-3-642-37486-9
Department/School
School of Information and Communication Technology
Publisher
Springer-
Place of publication
Berlin, Germany
Event title
The 18th International Conference on Database Systems for Advanced Applications
Event Venue
Wuhan, China
Date of Event (Start Date)
2013-04-22
Date of Event (End Date)
2013-04-25
Rights statement
Copyright 2013 Springer
Repository Status
Restricted
Socio-economic Objectives
Information systems, technologies and services not elsewhere classified