NOVA: A novel and efficient framework for finding subgraph isomorphism mappings in large graphs

Publication Type:
Conference Proceeding
Citation:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, 5981 LNCS (PART 1), pp. 140 - 154
Issue Date:
2010-12-28
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005465OK.pdf311.45 kB
Adobe PDF
Considerable efforts have been spent in studying subgraph problem. Traditional subgraph containment query is to retrieve all database graphs which contain the query graph g. A variation to that is to find all occurrences of a particular pattern(the query) in a large database graph. We call it subgraph matching problem. The state of art solution to this problem is GADDI. In this paper, we will propose a more efficient index and algorithm to answer subgraph matching problem. The index is based on the label distribution of neighbourhood vertices and it is structured as a multi-dimensional vector signature. A novel algorithm is also proposed to further speed up the isomorphic enumeration process. This algorithm attempts to maximize the computational sharing. It also attempts to predict some enumeration state is impossible to lead to a final answer by eagerly pruning strategy. We have performed extensive experiments to demonstrate the efficiency and the effectiveness of our technique. © Springer-Verlag Berlin Heidelberg 2010.
Please use this identifier to cite or link to this item: