Improved approach of calculating the same shape in graph mining (그래프 마이닝에서 그래프 동형판단연산의 향상기법)

노영상; Unil Yun (윤은일); KIM MYUNG JUN (김명준)

Improved approach of calculating the same shape in graph mining

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2009, 14(10), pp.251-258
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

노영상 ¹, Unil Yun ¹, KIM MYUNG JUN ¹

¹충북대학교

Accredited

ABSTRACT

Data mining is a method that extract useful knowledges from huge size of data. Recently, a focussing research part of data mining is to find interesting patterns in graph databases. More efficient methods have been proposed in graph mining. However, graph analysis methods are in NP-hard problem. Graph pattern mining based on pattern growth method is to find complete set of patterns satisfying certain property through extending graph pattern edge by edge with avoiding generation of duplicated patterns. This paper suggests an efficient approach of reducing computing time of pattern growth method through pattern growth's property that similar patterns cause similar tasks. we suggest pruning methods which reduce search space. Based on extensive performance study, we discuss the results and the future works.

KEYWORDS

서브 그래프 마이닝 (Subgraph mining), 패턴 확장 (pattern extension), 동형 그래프 동형 판단 (the same graph shape estimation)

Citation status

* References for papers published after 2023 are currently being built.

[confproc] R. Agrawal / 1993 / Mining association rules between sets of items in large datasets / In Proceedings of SIGMOD

[confproc] T. Asai / 2002 / Efficient substructure discovery from large semi-structured data / In Proceedings of KDD'04 SIAM SDM'02

[book] J. Han / 2005 / Data Mining : Concepts and Techniques / Morgan Kaufmann. Publishers

[confproc] J. Huan / Efficient mining of frequent subgraphs in the presence of isomorphism / In Proceedings of the Third IEEE International Conference on Data Mining (ICDM‘03)

[confproc] J. Huan / SPIN: mining maximal frequent subgraphs from graph databases / KDD '04: In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

[confproc] A. Inokuchi / An apriori-based algorithm for mining frequent substructures from graph data / In Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Disco (2000)

[journal] M. Kuramochi / 2004 / An Efficient Algorithm for Discovering Frequent Subgraphs / In Proceedings of IEEE Trans. Knowl. Data Eng. 16(9) : 1038~1051

[confproc] S. Nijssen / A quickstart in frequent structure mining can make a difference / In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD'04)

[confproc] N. Vanetik / 2004 / Mining Frequent Labeled and Partially Labeled Graph Patterns / In Proceedings of the International Conference on Data Engineering 2004 (ICDE2004)

[confproc] X. Yan / gSpan: Graph-based substructure pattern mining / In Proceedings of the 2002 IEEE International Conference on Data Mining

[confproc] X. Yan / 2003 / CloseGraph: Mining Closed Frequent Graph Patterns / In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

[confproc] F. Zhu / gPrune: A Constraint Pushing Framework for Graph Pattern Mining / In Proceedings of Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'07)

[journal] 산사볼트 가람라흐차 / 2009 / Searching Sequential Patterns by Approximation Algorithm / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 14(5) : 29~36

[journal] 오승준 / 2009 / Development of Automatic Rule Extraction Method in Data Mining : An Approach based on Hierarchical Clustering Algorithm and Rough Set Theory / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 14(6) : 135~142

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65