Graph Query Algorithms Research Over Dynamic Graph Data

Graph is applied to various fields as a kind of complex data structure, such as molecular chemistry and social networks. Graph query has attracted wide attention of scholars as an important topic of graph database management in recent years. Graph query problem is to find the qualified datagraph set from graph database, is divided into subgraph query and supergraph query. With the increasing amount of data, graph query provides users with more powerful and more comprehensive functions on the one hand. On the other hand, it makes the query process and indexing more complex. Therefore, it is crucial to make graph query efficiently on both static and dynamic graph data.At present, there is a lot of work committed to solve the problem of graph query. Most of the work use the "Filter-Verification" framework to handle graph query, mainly focus on constructing index and other data structures to filter out some non-result set in advance. Then query graph does subgraph isomorphism testing with graphs in candidate set individually. Ultimately, the method gets the result set. Existing methods can be divided into feature-based filtering and non-feature-based filtering, are all based on static datagraph. Nevertheless, in real life most of the graph data are frequently updated, and the cost of existing methods for frequently updated graph data is higher. Graph query is a NP complete problem, while frequently updated graph queries will become more difficult.In the light of the above problem this paper proposes the method of subgraph queries over dynamic graph data and the method of supergraph queries over incremental graph data. The first method constructs every graph's topological hierarchical sequence as index firstly, then filters out the candidate set according to the sequence matching relationship, and finally uses graph isomorphism algorithm to verify the candidate set then we can get final result set. The index is constructed easily and its size is small. The method doesn't need to rebuild index after database updating, and it not only supports subgraph queries on dynamic graph data, but also shows good performance on static graph data. The second method is based on the "Divide and Conquer" thought, decompose datagraph until the datagraph has only one vertex, then judge whether it is a subgraph to the query graph from one vertex graph to the whole datagraph. The advantage is that when datagraphs increase the method only need to "decompose the newly added datagraphs and dosen't need to query again.Time complexity doesn't have a linear growth with the datagraphs increasing. Generally the method saves time and space cost.Finally, many experiments on real data sets are made. Experimental results and analysis of experimental results prove that the proposed methods are capable of solving graph query problems on both static and dynamic graph data efficiently.