You are in:Home/Publications/Compressed Feature-based Filtering and Verification Approach for Subgraph Search. EDBT (2013) 287-298.

Prof. karam gouda :: Publications:

Compressed Feature-based Filtering and Verification Approach for Subgraph Search. EDBT (2013) 287-298.
Authors: Karam Gouda and Mosab hassaan
Year: 2013
Keywords: Data mining; outlier detection; data streams; density-based approach; clustering-based approach
Journal: (IJACSA) International Journal of Advanced Computer Science and Applications
Volume: 12
Issue: 11
Pages: 749 - 756
Publisher: Not Available
Local/International: International
Paper Link: Not Available
Full paper karam gouda_Paper_85-A_Fast_and_Efficient_Algorithm_for_Outlier_Detection.pdf
Supplementary materials Not Available

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