Graph Querying Using Graph Code and GC_Trie

Abstract

Graph datasets face a great challenge arising from a massive increasing volume of new structural graphs in bio-informatics, chem-informatics, and business processes, etc. One of the essential functions in graph dataset is to query graph effectively and efficiently. Given a graph query, it is desirable to retrieve relevant graphs quickly from a graph dataset via efficient graph indices. In our proposed system, there are two phases: index constructing and graph querying. In index constructing phase, a graph is represented holistically via graph code that is constructed based on adjacent edge information and edge dictionary. The graph code trie (GC_Trie) is constructed as index with graph codes of dataset graphs. In graph querying phase, automorphic(duplicate) graphs and isomorphic graphs of the query graph are queried by using GC_Trie as index. AIDS antiviral screen compound dataset is used to test the effectiveness of proposed approach. The experimental results offer a positive response to our newly proposed approach.