Pattern Match Query in a Large Uncertain Graph
Pattern Match Query in a Large Uncertain Graph
复制标题
DOI：
10.1145/2661829.2661868
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Ye Yuan;Guoren Wang;Lei Chen
中科院分区：
文献类型：
--
作者：
Ye Yuan;Guoren Wang;Lei Chen
对于图上的模式匹配问题，人们已经进行了大量的研究。这种兴趣在很大程度上是由于在许多领域的大量应用，这些领域需要高效的模式匹配解决方案，包括蛋白质复合体预测、社会网络分析和结构模式识别。然而，在许多实际应用中，图形数据往往是噪声、不完整和不准确的。换句话说，存在许多不确定图。因此，本文研究了大型不确定图中的模式匹配问题。具体地说，我们希望在不确定图中检索查询模式的所有合格匹配。虽然不确定图上的模式匹配是NP难的，但我们使用了过滤和验证框架来加快搜索速度。在过滤阶段，我们提出了一种基于匹配割集的概率匹配树PM-tree。在PM-树的基础上，我们设计了一种集体剪枝策略来剪枝大量不合格的匹配。在验证阶段，我们开发了一种有效的抽样算法来验证剩余的候选对象。大量的实验结果证明了该算法的有效性和高效性。
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.