Research On Graph Query Based On Non-mining Graph Index

The field of graph databases and graph query processing has received a lot ofattention due to the constantly increasing usage of graph data structure forrepresenting data in different domains such as: chemical compounds, multimediadatabases, social networks, protein networks and semantic web. In order to understandand utilize the graph database, we need a elementary mechanisms to efficientlysupport graph querying currently. Hence, determining graph database members whichconstitute the answer set of a graph query q from a large graph database is a keyperformance issue in all graph-based applications. Efficiently subgraph queryprocessing in large graph database is the key challenge. Because the subgraph query isan NP-complete problem currently, many algorithms improve the performance withgraph feature based index in subgraph query. But it is difficult and costly to keep theindexes dynamically as the feature is changing with the increasing database. So wepropose a efficient index technology and subgraph query method for undirected cyclicgraph databases which contain small graphs and many overlaps.In this paper, our main work is to get an efficient index structure for the graphswith small size and a lot of overlap. The applications of small graphs include Proteinstructure motifs and Chemical structures. We propose a new method to index graphdatabases so that we can do subgraph isomorphism queries and similarity queriesefficiently. The index is mainly includes two data structures. One of the key structuresis a directed acyclic graph. The nodes in this graph are the subgraphs of the databasegraphs, and every node is different from each other. If there are edges from node P tonode Q, it means that the graph presented by node P is the subgraph of the graphwhich is presented by node Q. This feature of the index is useful for us to implementsubgraph query. An install structure for the index and an algorithm of constructingindex is given in this paper. A hash table is the other main structure according to ourindex. The hash table indexes each subgraph so that we can lookup isomorphic fast.To create a hash key independent isomorphic, we use a code-based canonical torepresent an adjacency matrix. In order to increase computing speed, we also havefurther improved this representation. The structure of hash table and the hash functionare given in this paper. We also propose two subgraph query algorithm, and illustratethe process of the two queries. We conducted experiments on two practical datasets, and validate this concept through a consideration of the effectiveness of indexing andquery results. We do the experiment of subgraph isomorphism and similarity queriesin the two datasets. The experiment results show that our method is superior toconventional methods in a large extent.