Threshold-Based Shortest Path Query over Large Correlated Uncertain Graphs
Threshold-Based Shortest Path Query over Large Correlated Uncertain Graphs作者机构：College of Information Science and Engineering Northeastern University Shenyang 110819 China Department of Computer Science and Engineering Hong Kong University of Science and Technology Hong Kong China
出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)
年 卷 期：2015年第30卷第4期
页 面：762-780页
核心收录：
学科分类：02[经济学] 0808[工学-电气工程] 07[理学] 08[工学] 070103[理学-概率论与数理统计] 0202[经济学-应用经济学] 020208[经济学-统计学] 082303[工学-交通运输规划与管理] 0835[工学-软件工程] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 0811[工学-控制科学与工程] 082302[工学-交通信息工程及控制] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程]
基 金：This work is supported in part by the National Natural Science Foundation of China under Grant Nos. 61332006 U1401256 61328202 61173029 the Fundamental Research Funds for the Central Universities of China under Grant No. N130504006 the Hong Kong RGC Project under Grant No. N_HKUST637/13 the National Basic Research 973 Program of China under Grant No. 2014CB340300 Microsoft Research Asia Gift Grant and Google Faculty Award 2013
主 题：shortest path correlated uncertain graph probabilistic shortest path index
摘 要：With the popularity of uncertain data, queries over uncertain graphs have become a hot topic in the database community. As one of the important queries, the shortest path query over an uncertain graph has attracted much attention of researchers due to its wide applications. Although there are some e？cient solutions addressing this problem, all existing models ignore an important property existing in uncertain graphs： the correlation among the edges sharing the same vertex. In this paper, we apply Markov network to model the hidden correlation in uncertain graphs and compute the shortest path. Unfortunately, calculating the shortest path and corresponding probability over uncertain graphs modeled by Markov networks is a #P-hard problem. Thus, we propose a filtering-and-verification framework to accelerate the queries. In the filtering phase, we design a probabilistic shortest path index based on vertex cuts and blocks of a graph. We find a series of upper bounds and prune the vertices and edges whose upper bounds of the shortest path probability are lower than the threshold. By carefully picking up the blocks and vertex cuts, the index is optimized to have the maximum pruning capability, so that we can filter a large number of vertices which make no contribution to the final shortest path query results. In the verification phase, we develop an e？cient sampling algorithm to determine the final query answers. Finally, we verify the e？ciency and effectiveness of our solutions with extensive experiments.
维普期刊数据库