Research Of Multi-scale Parallel Subgraph Matching Algorithm In Cluster

As data has grown explosively,it's necessary for lots of system to process large scale data in the distribute system.As the data based on graph model has increased impressively,the graph algorithms based on cluster instead are in need.As one of the most complicate NP hard problem subgraph matching to solve,Subgraph matching have a wide area of application including pattern matching in social network,graph isomorphism in macromolecule and procedure pattern.However its complication still make existing method poses great shortages.We proposed a new subgraph matching approach in vertex based graph framework in the distributed system.Firstly,we use query tree instead of query graph to guide the matching order of matching procedure,and strategy to choose the query tree which would lead to the most stable matching procedure.Then,we use multi-scale parallel strategy,which include the parallel procedure between processes,data nodes and matching results,to explore the full potential of the cluster,which improves not only the utilization of cluster but also the efficiency of our method.Last but not least,we use simplified intermediate matching result,which would contribute to the useless intermediate result filtering,instead of complete matching result during communication between processes.In real world application,we use subgraph matching datasets and RDF datasets as an example to prove the performance of our approach,which is efficient,stable and scalable.