Pattern match query in a large uncertain graph

Many studies have been conducted on seeking an efficient solution for pattern matching over graphs. This interest is largely due to large number of applications in many fields, which require efficient solutions for pattern matching, including protein complex prediction, social network analysis and structural pattern recognition. However, in many real applications, the graph data are often noisy, incomplete, and inaccurate. In other words, there exist many uncertain graphs. Therefore, in this paper, we study pattern matching in a large uncertain graph. Specifically, we want to retrieve all qualified matches of a query pattern in the uncertain graph. Though pattern matching over an uncertain graph is NP-hard, we employ a filtering-and-verification framework to speed up the search. In the filtering phase, we propose a probabilistic matching tree, PM-tree, based on match cuts obtained by a cut selection process. Based on PM-tree, we devise a collective pruning strategy to prune a large number of unqualified matches. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. Extensive experimental results demonstrate the effectiveness and efficiency of the proposed algorithms.