HOME     |      PUBLICATIONS     |      PROJECTS     |      TEACHING     |      RESOURCES         

Ekaterini Ioannou

Software Technology and Network Applications Laboratory

Department of Electronic & Computer Engineering
Technical University of Crete
University Campus
73100, Crete, HELLAS

ioannou AT softnet.tuc.gr
EkateriniIoannou AT acm.org

Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases

Odysseas Papapetrou, Ekaterini Ioannou, and Dimitrios Skoutas.
In Proceedings of the 14th International Conference on Extending Database Technology (EDBT), Mar. 2011, Sweden.


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.


     author = {Odysseas Papapetrou and Ekaterini Ioannou and Dimitrios Skoutas},
     title = {Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases},
     booktitle = {EDBT},
     year = {2011},
     pages = {355-366}

Last modified: April 2011