SASUM: A Sharing-Based Approach to Fast Approximate Subgraph Matching for Large Graphs
スポンサーリンク
概要
- 論文の詳細を見る
Subgraph matching is a fundamental operation for querying graph-structured data. Due to potential errors and noises in real-world graph data, exact subgraph matching is sometimes inappropriate in practice. In this paper we consider an approximate subgraph matching model that allows missing edges. Based on this model, approximate subgraph matching finds all occurrences of a given query graph in a database graph, allowing missing edges. A straightforward approach is to first generate query subgraphs of a given query graph by deleting edges and then perform exact subgraph matching for each query subgraph. In this paper we propose a sharing-based approach to approximate subgraph matching, called SASUM. Our method is based on the fact that query subgraphs are highly overlapped. Due to this overlapping nature of query subgraphs, the matches of a query subgraph can be computed from the matches of a smaller query subgraph, which results in reducing the number of query subgraphs that require expensive exact subgraph matching. Our method uses a lattice framework to identify sharing opportunities between query subgraphs. To further reduce the number of graphs that need exact subgraph matching, SASUM generates small base graphs that are shared by query subgraphs and chooses the minimum number of base graphs whose matches are used to derive the matching results of all query subgraphs. A comprehensive set of experiments shows that our approach outperforms the state-of-the-art approach by orders of magnitude in terms of query execution time.
著者
-
Lee Yoon-joon
Department Of Computer Science Kaist
-
LEE Kyong-Ha
Department of Computer Science, KAIST
-
KIM Song-Hyon
Department of Computer Science, KAIST
-
SONG Inchul
Department of Computer Science, KAIST
関連論文
- Accelerating Database Processing at Database-Driven Web Sites(Contents Technology and Web Information Systems)
- B208 ESTIMATION OF SPATIALLY VARYING THERMAL CONDUCTIVITY WITHOUT INTERNAL MEASUREMENTS(Gas turbine & forced convection heat transfer)
- Dynamic Forest : An Efficient Index Structure for NAND Flash Memory
- An Efficient Dynamic Hash Index Structure for NAND Flash Memory
- An Effective Self-Adaptive Admission Control Algorithm for Large Web Caches
- Concept Drift Detection for Evolving Stream Data
- SASUM: A Sharing-Based Approach to Fast Approximate Subgraph Matching for Large Graphs