Efficient pattern matching on big uncertain graphs
Efficient pattern matching on big uncertain graphs
复制标题
DOI：
10.1016/j.ins.2015.12.034
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Ye Yuan;Guoren Wang;Lei Chen;B. Ning
中科院分区：
文献类型：
--
作者：
Ye Yuan;Guoren Wang;Lei Chen;B. Ning
大量研究致力于寻找图模式匹配问题的有效解决方案。这种兴趣很大程度上是由于许多应用需要这种有效的解决方案，包括蛋白质复合物预测、社交网络分析和结构模式识别。然而，在许多实际应用中，图数据往往是有噪声的、不完整的、不准确的。换句话说，存在许多不确定的图。因此，在本文中，我们研究大型不确定图背景下的模式匹配。具体来说，我们想要检索不确定图中查询模式的所有合格匹配项。尽管不确定图上的模式匹配是 NP 困难的，但我们采用过滤和验证框架来加速搜索。在过滤阶段，我们提出了根据剪切选择过程获得的匹配剪切构建的概率匹配树（PM-tree）。基于PM树，我们设计了一种集体剪枝策略来剪枝大量不合格的匹配。在验证阶段，我们开发了一种有效的采样算法来验证剩余的候选者。大量的实验结果证明了所提出算法的有效性和效率。最后，我们展示了如何将我们的解决方案应用于查询知识图。
A significant amount of research has been devoted to seeking efficient solutions to the problem of pattern matching over graphs. This interest is largely due to the many applications that require such efficient solutions, 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 the context of large uncertain graphs. Specifically, we want to retrieve all qualified matches of a query pattern in the uncertain graph. Though pattern matching over uncertain graphs is NP-hard, we employ afiltering-and-verificationframework to speed up the search. In the filtering phase, we propose aprobabilistic matching tree(PM-tree) built from match cuts obtained by a cut selection process. Based on the PM-tree, we devise acollective pruningstrategy 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. Finally, we show how our solution can be applied to querying knowledge graphs.