Efficient pattern matching on big uncertain graphs

Ye Yuan*, Guoren Wang, Lei Chen, Bo Ning

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

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 a filtering-and-verification framework to speed up the search. In the filtering phase, we propose a probabilistic matching tree (PM-tree) built from match cuts obtained by a cut selection process. Based on the 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. Finally, we show how our solution can be applied to querying knowledge graphs.

Original languageEnglish
Pages (from-to)369-394
Number of pages26
JournalInformation Sciences
Volume339
DOIs
Publication statusPublished - 20 Apr 2016
Externally publishedYes

Keywords

  • Graph data
  • Uncertain data

Fingerprint

Dive into the research topics of 'Efficient pattern matching on big uncertain graphs'. Together they form a unique fingerprint.

Cite this