Efficient Identification of Frequent Family Subtrees in Tree Database

Abstract:

This paper introduces a new type of problem called the frequent common family subtree mining problem for a collection of leaf-labeled trees and presents some characteristics for the problem. It proposes an algorithm to find frequent common families in trees. To its applicability, the proposed method has been applied to both several synthetic data sets and a real data set.

• Periodical: Applied Mechanics and Materials (Volumes 241-244)
• Pages: 3165-3170
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.241-244.3165
• Online since: December 2012
• Authors: Kyung Mi Lee, Keon Myung Lee
• Keywords: Data Analysis, Data Mining (DM), Family Subtree, Leaf-Labeled Trees, Tree Mining

References

[1] A. Rajaraman, J. D. Ullman: Mining of Massive Datasets, Cambridge University Press (2012).

[2] R. Agrawal, R. Srikant: Fast Algorithms for Mining Association Rules. In: Proc. of Int. Conf. on Very Large Data Bases, (1994).

[3] Y. Chi, S. Nijssen, R. R. Muntz, J. N. Kok: Frequent Subtree Mining – An Overview. Foundamenta Informaticae, 11 (2005) 1001-1038.

[4] D. Charkrabarti, C. Faloutsos: Graph Mining: Laws, Generators, and Algorithms. ACM Computing Surveys, 38 (2006) 1-69.

DOI: 10.1145/1132952.1132954

[5] R. A. Mohammadzadeh, M. H. Chehreghani, A. Zarnani, M. Rahgozar: W3-Miner: Mining Weighted Frequent Subtree Patterns in a Collection of Trees. Int. Journal of Engineering and Applied Sciences, 1(1) (2005) 60-63.

[6] A. Deepak, D. Frenandez-Baca, S. Tirthapura, M. J. Sanderson, M. M. McMahon: EvoMiner: Frequent Subtree Mining in Phylogenetic Databases, Technical Report 11-08, Computer Science, Iowa State University (2011).

DOI: 10.1007/s10115-013-0676-0

[7] K. M. Lee, K. M. Lee: Medoid Determination in Deterministic Annealing-based Pairwise Clustering, Int. J. of Fuzzy Logic and Intelligent Systems, 11(3) (2011) 178-183.

DOI: 10.5391/ijfis.2011.11.3.178

[8] S. Zhang, J. T. L. Wang: Mining Frequent Agreement Subtrees in Phylogenetic Databases, In: Proc. of the 6th SIAM Int. Conf. on Data Mining, (2006) 222-233.

DOI: 10.1137/1.9781611972764.20

[9] S. Zhang, J. T. L. Wang: Discovering Frequent Agreement Subtrees from Phylogenetic Data, IEEE Trans. on Knowledge and Engineering, 20(1) (2008) 1-15.

DOI: 10.1109/tkde.2007.190676

[10] M. Nei, S. Kumar: Molecular Evolution and Phylogenetics, (2000).

[11] F. Luccio, A. M. Enriquz, P.O. Rieumont, L. Pagli: Bottom-up Subtree Isomorphism for Unordered Labeled Trees, Technical Report TR-01-14, Universita Di Pisa (2004).

[12] M. J. Zaki.: Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications. IEEE Trans. on Knowledge and Data Engineering, 17(8) (2005).

DOI: 10.1109/tkde.2005.125

[13] T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Satamoto, S. Arikawa.: Efficient Substructure Discovery from Large Semi-Structured Data, In: Proc. of 2nd SIAM Int. Conf. on Data Mining (2002).

DOI: 10.1137/1.9781611972726.10

[14] T. Asai, H. Arimura, T. Uno, S. Nakano: Discovering Frequent Substructures in Large Unordered Trees. In: Proc. of the 6th Int. Conf. on Discovery Science (2003).

DOI: 10.1007/978-3-540-39644-4_6

[15] S. Nijssen, J. N. Kok: Efficient Discovery of Frequent Unordered Trees. In: Proc. of First Int. Workshop on Mining Graphs, Trees and Sequences (2003).