摘要
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.
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.
基金
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.
