DistR: A Distributed Method for the Reachability Query over Large Uncertain Graphs
DistR: A Distributed Method for the Reachability Query over Large Uncertain Graphs
复制标题
DOI：
10.1109/tpds.2016.2535444
复制
发表时间：
2016-11
影响因子：
5.3
通讯作者：
Yurong Cheng;Ye Yuan;Lei Chen;Guoren Wang;C. Giraud-Carrier;Yongjiao Sun
中科院分区：
文献类型：
--
作者：
Yurong Cheng;Ye Yuan;Lei Chen;Guoren Wang;C. Giraud-Carrier;Yongjiao Sun
在不确定图查询中，可达性，即，一个顶点从另一个顶点可达的概率可能是最基本的概率。虽然这个问题已经在网络可靠性领域进行了研究，但解决方案只能在一台计算机上实现，并且只能处理小图形。然而，随着图形应用程序的大小不断增加，相应的图形数据不再适合单个计算机的内存，因此必须分布在多台机器上。此外，概率可达性查询的计算是#P-完全的，即使在小图上也非常昂贵。在本文中，我们开发了一个有效的分布式策略，称为DistR，来解决大型不确定图的可达性查询问题。具体来说，我们分两步执行任务：分布式图简化和分布式合并。在分布式图约简步骤中，我们找到原始图的所有最大子图，其可达概率可以在多项式时间内计算，计算它们并相应地约简图。在这一步之后，只剩下一个小图形。在分布式合并步骤中，我们将问题转换为关系连接过程，并提供了一个近似的答案，以#P-完全可达性查询。大量的实验研究表明，我们的分布式方法是有效的计算和通信成本方面，并具有较高的精度。
Among uncertain graph queries, reachability, i.e., the probability that one vertex is reachable from another, is likely the most fundamental one. Although this problem has been studied within the field of network reliability, solutions are implemented on a single computer and can only handle small graphs. However, as the size of graph applications continually increases, the corresponding graph data can no longer fit within a single computer's memory and must therefore be distributed across several machines. Furthermore, the computation of probabilistic reachability queries is #P-complete making it very expensive even on small graphs. In this paper, we develop an efficient distributed strategy, called DistR, to solve the problem of reachability query over large uncertain graphs. Specifically, we perform the task in two steps: distributed graph reduction and distributed consolidation. In the distributed graph reduction step, we find all of the maximal subgraphs of the original graph, whose reachability probabilities can be calculated in polynomial time, compute them and reduce the graph accordingly. After this step, only a small graph remains. In the distributed consolidation step, we transform the problem into a relational join process and provide an approximate answer to the #P-complete reachability query. Extensive experimental studies show that our distributed approach is efficient in terms of both computational and communication costs, and has high accuracy.