The week's pick
Random Articles
Reseach Article
DAGC: Identification and Filtration of Automorphic Graphs in Graph Databases
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 30 - Number 4 |
| Year of Publication: 2011 |
| Authors: Aye Nwe Thaing, Kyaw May Oo |
10.5120/3632-5072
|
Aye Nwe Thaing, Kyaw May Oo . DAGC: Identification and Filtration of Automorphic Graphs in Graph Databases. International Journal of Computer Applications. 30, 4 ( September 2011), 8-13. DOI=10.5120/3632-5072
Abstract
Graphs are the ubiquitous models for constructing both natural and human-made structures. Many practical problems can be represented by graphs. They can be used to model many applications such as physical, biological and social systems. With the emergence of these applications, developments of graph databases are very useful to store graph data. Due to the existence of noise (e.g., duplicated graphs) in the graph database, we investigate the problem of storing the same graphs in the single graph database. Therefore, detecting and eliminating of automorphic graphs in a graph database become an important research area. In this paper, we propose a novel DAGC algorithm to identify and removal of automorphic graph storing into the graph database using AdE index structure. AdE index structure incorporates graph structural information of each graph in the database. The computational time complexity is significantly reduced compared to canonical labeling approach used in most graph matching algorithms and F-GAF algorithm. This paper demonstrates the effectiveness and efficiency of the proposed method through experiments on various types of graphs.
References
- M. Kuramochi and G. Karypis. Frequent Subgraph Discovery. Proc. 1st IEEE Int. Conf. on Data Mining (ICDM 2001), San Jose, CA), 313–320. IEEE Press, Piscataway, NJ, USA 2001
- R Vijayalakshmi, R Nadarajan, P Nirmala, and M Thilaga. A Novel Approach for Detection and Elimination of Automorphic Graphs in Graph Databases. Int. J. Open Problems Compt. Math., Vol. 3, No. 1, March 2010
- R. N. Chittimoori, L. B. Holder, and D. J. Cook. Applying the SUBDUE substructure discovery system tothe chemical toxicity domain. In Proc. of the 12th International Florida AI Research Society Conference, pages 90–94, 1999
- L. Dehaspe, H. Toivonen, and R. D. King. Finding frequent substructures in chemical compounds. In R. Agrawal, P. Stolorz, and G. Piatetsky-Shapiro, editors, Proc. of the 4th International Conference on Knowledge Discovery and Data Mining, pages 30–36. AAAI Press, 1998.
- H. K¨alvi¨ainen and E. Oja. Comparisons of attributed graph matching algorithms for computer vision. In Proc. of STEP-90, Finnish Artificial Intelligence Symposium, pages 354– 368, Oulu, Finland, June 1990.
- D. A. L. Piriyakumar and P. Levi. An efficient A* based algorithm for optimal graph matching appliedto computer vision. In GRWSIA-98, Munich, 1998.
- D. W. Williams, J. Huan, W. Wang. “Graph Database Indexing Using Structured Graph Decomposition”, 2007.
- R. Agrawal and R. Srikant. Mining sequential patterns. In P. S. Yu and A. L. P. Chen, editors, Proc. Of the 11th Int. Conf. on Data Engineering (ICDE), pages 3–14. IEEE Press, 1995.
- S. Fortin. The graph isomorphism problem. Technical Report TR96-20, Department of Computing Science, University of Alberta, 1996.
- J. Huan, W. Wang, and J. Prins, “Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs”, Journal of Computational Biology(JCB), Vol.12, No.6, pp.6576671,2005.
Index Terms
Keywords