Efficient discovery of frequent subgraph patterns in uncertain graph databases

Odysseas Papapetrou, Ekaterini Ioannou, Dimitrios Skoutas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

22 Citations (Scopus)

Abstract

Mining frequent subgraph patterns in graph databases is a challenging and important problem with applications in several domains. Recently, there is a growing interest in generalizing the problem to uncertain graphs, which can model the inherent uncertainty in the data of many applications. The main difficulty in solving this problem results from the large number of candidate subgraph patterns to be examined and the large number of subgraph isomorphism tests required to find the graphs that contain a given pattern. The latter becomes even more challenging, when dealing with uncertain graphs. In this paper, we propose a method that uses an index of the uncertain graph database to reduce the number of comparisons needed to find frequent subgraph patterns. The proposed algorithm relies on the apriori property for enumerating candidate subgraph patterns efficiently. Then, the index is used to reduce the number of comparisons required for computing the expected support of each candidate pattern. It also enables additional optimizations with respect to scheduling and early termination, that further increase the efficiency of the method. The evaluation of our approach on three real-world datasets as well as on synthetic uncertain graph databases demonstrates the significant cost savings with respect to the state-of-the-art approach.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2011
Subtitle of host publication14th International Conference on Extending Database Technology, Proceedings
Pages355-366
Number of pages12
DOIs
Publication statusPublished - 18 Apr 2011
Externally publishedYes
Event14th International Conference on Extending Database Technology: Advances in Database Technology, EDBT 2011 - Uppsala, Sweden
Duration: 22 Mar 201124 Mar 2011

Conference

Conference14th International Conference on Extending Database Technology: Advances in Database Technology, EDBT 2011
CountrySweden
CityUppsala
Period22/03/1124/03/11

Keywords

  • Algorithms
  • Theory

Fingerprint Dive into the research topics of 'Efficient discovery of frequent subgraph patterns in uncertain graph databases'. Together they form a unique fingerprint.

  • Cite this

    Papapetrou, O., Ioannou, E., & Skoutas, D. (2011). Efficient discovery of frequent subgraph patterns in uncertain graph databases. In Advances in Database Technology - EDBT 2011: 14th International Conference on Extending Database Technology, Proceedings (pp. 355-366) https://doi.org/10.1145/1951365.1951408