## 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 language | English |
---|---|

Title of host publication | Advances in Database Technology - EDBT 2011 |

Subtitle of host publication | 14th International Conference on Extending Database Technology, Proceedings |

Pages | 355-366 |

Number of pages | 12 |

DOIs | |

Publication status | Published - 18 Apr 2011 |

Externally published | Yes |

Event | 14th International Conference on Extending Database Technology: Advances in Database Technology, EDBT 2011 - Uppsala, Sweden Duration: 22 Mar 2011 → 24 Mar 2011 |

### Conference

Conference | 14th International Conference on Extending Database Technology: Advances in Database Technology, EDBT 2011 |
---|---|

Country/Territory | Sweden |

City | Uppsala |

Period | 22/03/11 → 24/03/11 |

## Keywords

- Algorithms
- Theory