Scalable processing of massive uncertain graph data: A simultaneous processing approach

This paper studies a novel approach to processing massive uncertain graph data. In this approach, we propose a new framework to simultaneously process a query on a set of randomly sampled possible worlds of an uncertain graph. Based on this framework, we develop a series of algorithms to analyze massive uncertain graphs, including breadth-first search, shortest distance queries, triangle counting, and core decomposition. We implement this approach based on GraphLab, one of the stateof-The-Art graph processing frameworks. By sharing fine-grained internal processing steps on common substructures of sampled possible worlds, the new approach achieves tens to hundreds of times speedup in execution time on a cluster of 20 servers.