Font Size: a A A

Research Of Subgraph Isomorphism Search Algorithm On Graph Data

Posted on:2016-09-04Degree:MasterType:Thesis
Country:ChinaCandidate:Y HanFull Text:PDF
GTID:2308330479451074Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Graph is a universal data structure which is prevalently used for modeling complex structures such as molecules interaction networks and program dependence, and so on. With the expanding of graph data scale, efficient graph data management has become one of hotspots which researchers focus on. The subgraph isomorphism search is one of the core problems in graph databases, which is to find all distinct mappings(or embeddings) of given a query graph in data graph. Although, in theory, subgraph isomorphism search belongs to NP-hard, we can efficiently improve the system efficiency in practice if we exploit a good matching order and powerful pruning techniques. The paper is the research of the subgraph isomorphism search in graph data management, and the research contents are organized as follows.Firstly, by thorough analysis for exist subgraph isomorphism algorithms, and find they all have some problems which affect the performance of subgraph isomorphism search:(1) redundant computations because of no best matching strategy;(2) redundant enumerations between query vertices and data vertices often lead to redundant computations;(3) the inefficiency of pruning strategy lead to redundant computations.Secondly, for these problems, we propose URSI(Ultrafast and Robust Subgraph Isomorphism)algorithm. It uses candidate region exploration to solve the matching strategy problem in subgraph isomorphism search, and propose COMB/PERM to solve the redundant enumeration problem between query vertices and data vertices. And URSI propose a new pruning strategy in the filtering stage which verifies non-tree edges in candidate region exploration to filter more data vertices. Thus, the number of candidate regions will be reduced, and the time of verification and subgraph isomorphism search will decrease.At last, the experimental results show that our method is much more efficient than existing ones according to various metrics.
Keywords/Search Tags:subgraph isomorphism search, subgraph query, candidate region exploration, pruning technique, COMB/PERM
PDF Full Text Request
Related items