Publication

Abstract : Graphs have become indispensable in modeling and representing complicated structured data such as proteins, chemical compounds, and XML documents. Development of graph databases for use in research and development is a well-established activity in pharmaceutical and chemical industries. Storing the graphs into large databases is a challenging task as it deals with efficient space and time management. Unlike item sets in huge transactional databases, it becomes essential to ensure the consistency of graph databases since relationships among edges of a graph are predominant. One of the necessary procedures required is a mechanism to check whether two graphs are automorphic. For graphs with more than one vertex with the same label, more than one adjacency matrix representations are possible based on the ordering of vertices with identical labels and there are possibilities that the same graph is stored more than once using different adjacency matrices, leading to adverse results in mining graph databases. Difficulty in identifying and eliminating the automorphic graphs is a challenging problem to the research community. In this paper, a proficient algorithm is devised that efficiently detects and avoids the same graph getting stored into the database. The computational time is also substantially reduced compared to the canonical labeling approach used in Frequent Subgraph Discovery algorithm. The experimental results and comparisons offer a positive response to the newly proposed algorithm.