You are in:Home/Publications/Compressed Feature-based Filtering and Verification Approach for Subgraph Search.

Dr. Mosab abd el-hameed mohamed hassaan :: Publications:

Title:
Compressed Feature-based Filtering and Verification Approach for Subgraph Search.
Authors: Karam Gouda and Mosab Hassaan
Year: 2013
Keywords: Not Available
Journal: Not Available
Volume: Not Available
Issue: Not Available
Pages: Not Available
Publisher: Not Available
Local/International: International
Paper Link: Not Available
Full paper Mosab abd el-hameed mohamed hassaan_Karam-Mosab-EDBT_Conference2013.pdf
Supplementary materials Not Available
Abstract:

Subgraph search in graph datasets is an important problem with numerous applications. Many feature-based indexing methods have been proposed for solving this problem. These methods have to index too many features or select some of them in order to get an index with good pruning capabilities. None of these directions can give an effective solution to all graph indexing issues. In this paper, we propose an efficient indexing approach which improves over current feature-based methods, neither by the costly feature selection nor by explicitly indexing a multitude of features. We achieve this by compressing multiple features into one feature with some neighborhood information en- coded. Neighborhood is further used to prune unmatched feature occurrences between the query and data graphs, thus cutting down the search space of subgraph matching, which significantly reduce the verification cost. We implement the approach by exhaustively enumerating small paths as features. A novel path-at-a-time verification method that benefits from the occurrences pruning method is introduced. Via an extensive evaluation on both real and synthetic datasets, we show that our approach is effective and scalable, and outperforms state-of-the-art indexing methods.

Google ScholarAcdemia.eduResearch GateLinkedinFacebookTwitterGoogle PlusYoutubeWordpressInstagramMendeleyZoteroEvernoteORCIDScopus