Compact Graph Representative Structure for Efficient Graph Querying in Chemical Compound Graph Databases

Abstract

Graph has become a powerful tool for representing and modeling objects and their relationships in various application domains such as protein interaction, social networks and chemical informatics. With the emergence of these applications, developments of graph databases are very useful to store graph data. However, performance query processing on graph database (GDB) is still inadequate due to the high complexity of processing graph data. As a result, effective graph structures to store graphs are the current research area to complete efficient query processing on the graph databases. In this paper, a new compact graph representative structure(CGRS) is proposed to perform efficient graph query processing. In CGRS, a graph is represented holistically via its edge code using edge dictionary. The idea of graph decomposition is used to specify all connected, induced subgraphs of a given graph without changing the structure of the original graphs. Using CGRS, two types of graph queries can be processed: graph isomorphism query and subgraph isomorphism query. Chemical compound dataset is applied to test the effectiveness of our proposed CGRS. The analysis of storage space, graph construction time and query response time offers a positive response to our newly proposed CGRS structure.