Pregel Based Graph Simulation Matching

Graph matching is an important technical method for the application of graph data.Compared with the matching method based on subgraph isomorphism,the graph simulation can effectively improve the graph matching efficiency because it reduces the structural matching requirements.However,in the case of large-scale graph data,the existing graph matching method based on graph simulation can still not meet the requirements of efficient matching.To solve this problem,based on the existing graph simulation methods,this paper presents a parallel graph matching method based on the Pregel programming model.The main research work and contributions of this article are as follows:Firstly,parallel query matching method based on Pregel programming model is proposed for two non-circular and circled query modes.For two different query modes,the message initialization,node message response and processing,message merging,and message processing methods of nodes based on the Pregel programming model are given respectively.Secondly,the correlation set is an important quality metric for graph matching,and its size can indicate the coverage of the pattern on the data map.For the "noncircle" and "circle" two query modes,a parallelized graph matching correlation set solving method based on the Pregel programming model is proposed.After that,GraphX,a parallel computing component based on the Spark platform,can implement graph simulation matching and correlation set solving methods based on the Pregel programming model.Finally,on the real data set,experiments verify the validity of the graph pattern matching algorithm based on the Pregel programming model proposed in this paper and the related set solving method.The experimental results show that the method proposed in this paper can significantly shorten the matching time,and improve the matching efficiency of the algorithm effectively.