Improving Continuous Subgraph Matching Over Graph Streams

With the wide application of uncertain graph database in analysising of compounds, intrusion detection on the network data stream and the pattern matching of the users’ access log, how to deal with the subgraph matching problem more effectively is becoming more and more important. Especially in recent years, the graph model of eht actual application is not constant, but changes over time, which brings a great challenge to the trauditional function of dealing with subgraph matching problem. However since subgraph isomorphism checking is an NP-complete problem, how to deal with the matching job online in real ime will be a horrible job.So there is a great need for a better algorithm to deal with the subgraph matching problem on graph stream. And the algorithm describe in this article is very meaningful.At present, thre are already lots of works committed to solve the problem of subgraph matching on graph stream. And among them, the method using NNTree index is the best. So based on the existing work, this article improves the NNTree index to MidIndex and proposes a new algorithm which directly uses the changes in the graph stream to match the query graph. So it reduces the number of updates of the index and improves the efficiency of the matching process.Then this article further improves the index structure through bringing edges’set which remember the sensitive edges.And as the edges’ set can help protect a isomorphic structure of query graph, the new matching method can still work well even the phenomena of continue matching occurs frequently. So the matching method can be more effective and stable.Finally, the author designs and builds a subgraph matching system over graph stream which can show the mathing process directly and a lot of experiments on real data sets are made on it. Experimental results and analysis of experimental results prove that the proposed algorithm is capable of solving subgraph matching problems on graph stream efficiently.