Efficient processing of label-constraint reachability queries in large   graphs

doi:10.1016/j.is.2013.10.003

CORC > 北京大学 > 信息科学技术学院

	Efficient processing of label-constraint reachability queries in large graphs
	Zou, Lei ; Xu, Kun ; Yu, Jeffrey Xu ; Chen, Lei ; Xiao, Yanghua ; Zhao, Dongyan
刊名	information systems
	2014
关键词	Graph database Reachability query
DOI	10.1016/j.is.2013.10.003
英文摘要	In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u(1) and u(2) in a large directed graph G, we check the existence of a directed path from u(1) to u(2), where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by redefining the "distance" of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method. (C) 2013 Elsevier Ltd. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000330090500004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Information Systems; SCI(E); EI; 1; ARTICLE; zoulei.hust@gmail.com; 47-66; 40
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/163207]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Zou, Lei,Xu, Kun,Yu, Jeffrey Xu,et al. Efficient processing of label-constraint reachability queries in large graphs[J]. information systems,2014.
APA	Zou, Lei,Xu, Kun,Yu, Jeffrey Xu,Chen, Lei,Xiao, Yanghua,&Zhao, Dongyan.(2014).Efficient processing of label-constraint reachability queries in large graphs.information systems.
MLA	Zou, Lei,et al."Efficient processing of label-constraint reachability queries in large graphs".information systems (2014).