Incremental Subgraph Similarity Match Technology Research And Implementation Over Streaming Graph

In recent years,with the graph structure widely used in communication networks,pattern recognition,chemical/biological information,social networks and the fast development of the diversity of data,streaming graph model has attracted more and more attention from experts and scholars.At present,the subgraph match technology over static graph has been researched extensively and deeply,however,the subgraph matching technology as the foundation of many other operations over streaming graph has not been researched thoroughly,and the steaming graph model has a wide range of values and profound realistic significance on many aspects,such as network security,social networks and so on.According to the above problems,this thesis focuses on the research on the issue of incremental subgraph similarity matching over steaming graphs.Firstly,this thesis considers simple update on steaming graphs,which means if there is an edge has already in the steaming graphs,we cannot insert the edge again.In order to achieve the ideal of incremental maintenance,this thesis designs a partition strategy.with pruning effects for steaming graphs,namely the nearest neighbor partition method,and incremental maintenance for it.For this,when an update operation arrives,we just need to maintain the changed partition,instead of a complete matching process.Considering the changing characteristics of steaming graphs,we implement the subgraph matching by creating spanning tree set for query graphs,which changes the matching from graph-graph to tree-graph to further improve the speed of subgraph matching.This thesis proposes the idea of maximum matching to avoid the expense of dealing with redundancy.Finally,the experiments are conducted on real data sets and synthetic data sets,and compared with the traditional methods over streaming graphs.It shows that the proposed method is correct and valid.In addition,this thesis also considers the complex updates over steaming graphs,i.e.the same edge can be inserted or deleted more than one time.The problem is the extension of the above problem.A nearest neighbor partition method based on weights is further proposed,and this method can prune the steaming graphs by weight judgment to speed up the match speed.At the same time in order to satisfy the real-time response characteristics of steaming graphs,an approximate match method is put forward.When an update operation arrives,this method directly conducts incremental maintenance on the results by maintaining the match results candidate set,to better accelerate the matching,and ensure the accuracy of the matching results through the proposed approximate error rate.Finally the effectiveness of the proposed method is verified by experiments.All in all,this thesis begins with the typical characteristics and challenges of the subgraph similarity match over streaming graphs which are increasingly involved in the real-life applications.The researches on simple updates and complex updates are explored separately.Based on the idea of incremental maintenance,an effective framework of incremental subgraph similarity match over streaming graph is proposed.The ideas such as incremental maintenance and nearest neighbor partition proposed in this thesis have also offered foundations for related subjects.