NOVA: A Novel and Efficient Framework for Finding Subgraph Isomorphism Mappings in Large Graphs

Publisher:
Springer
Publication Type:
Conference Proceeding
Citation:
LNCS - Database Systems for Advanced Applications - Part 1 Proceedings of the International Conference on Database Systems for Advanced Applications, 2010, 5981 pp. 140 - 154
Issue Date:
2010-01
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.
Please use this identifier to cite or link to this item: