The week's pick
Random Articles
Reseach Article
Batch Processing for Incremental FP-tree Construction
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 5 - Number 5 |
| Year of Publication: 2010 |
| Authors: PVGD Prasad Reddy, Geeta R. B., Shashikumar G. Totad |
10.5120/910-1288
|
PVGD Prasad Reddy, Geeta R. B., Shashikumar G. Totad . Batch Processing for Incremental FP-tree Construction. International Journal of Computer Applications. 5, 5 ( August 2010), 28-32. DOI=10.5120/910-1288
Abstract
Frequent Patterns are very important in knowledge discovery and data mining process such as mining of association rules, correlations etc. Prefix-tree based approach is one of the contemporary approaches for mining frequent patterns. FP-tree is a compact representation of transaction database that contains frequency information of all relevant Frequent Patterns (FP) in a dataset. Since the introduction of FP-growth algorithm for FP-tree construction, three major algorithms have been proposed, namely AFPIM, CATS tree, and CanTree, that have adopted FP-tree for incremental mining of frequent patterns. All of the three methods perform incremental mining by processing one transaction of the incremental database at a time and updating it to the FP-tree of the initial (original) database. Here in this paper we propose a novel method to take advantage of FP-tree representation of incremental transaction database for incremental mining. We propose “Batch Incremental Tree (BIT)” algorithm to merge two small consecutive duration FP-trees to obtain a FP-tree that is equivalent of FP-tree obtained when the entire database is processed at once from the beginning of the first duration to the end of the second duration. For large databases, our experimental results show significant reduction in runtime of the BIT algorithm compared to the runtime of sequential incremental algorithms.
References
- Paul S. Bradley, J. E. Gehrke, Raghu Ramakrishnan and Ramakrishnan Srikant. “Philosophies and Advances in Scaling Mining Algorithms to Large Databases”. Communications of the ACM, August 2002
- R.J. Bayardo , “Efficient mining of long patterns from databases”. In Proc. SIGMOD 1998, pp. 85-93.
- Agrawal R., Imielinski, T., and Swami, A. 1993. “Mining association rules between sets of items in large databases”. In Proc. of ACM-SIGMOD, 1993 (SIGMOD’93), pp. 207–216.
- Agrawal R, Srikant R. “Fast Algorithms for Mining Association Rules”. In Proc. of VLDB, Sep 2- 15 1994, pp. 487-99.
- D W Cheung, J. Han, V.T. Ng, and C.Y. Wong,”Maintenance of discovered association rules in large databases: an incremental updating technique”. In Proc. of ICDE 1996, pp. 106–114.
- F. Bonchi and C. Lucchese, “ On closed constrained frequent pattern mining”. In Proc ICDM 2004,pp. 35-42.
- Lee, C-H., Lin, C-R., & Chen, M.S., “Slid¬ing window filtering: an efficient method for incremental mining on a time-variant database”. In ELSEVIER-Information Systems,30(3), 2005, pp. 227-244.
- J. Han, J. Pei, Y. Yin and R. Mao, “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach”. Data Mining and Knowledge Discovery, 8(1), 2004, pp.53-87.
- Koh, J-L., & Shieh, S-F. “An Efficient Ap¬proach for Maintaining Association Rules Based on Adjusting FP-tree Structures”. Proceedings of the 2004 Database Systems for Advanced Applica¬tions, 2004, pp. 417-424.
- Cheung, W, & Zaïane, O. R.. “Incremental Mining of Frequent-patterns without Candidate Gneration or Support Constraint”. Proceedings of the 2003 International Database Engineering and Applications Symposium, 2003, pp. 111-116.
- Leung, C. K-S., Khan, Q. I., Li Z., & Hoque, T. “CanTree: A Tree Structure for Efficient Incremental Mining of Frequent Patterns”. Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM’05), 2005.
- D. W. cheung , S.D. Lee, and B. kao, ”A general incremental technique for maintaining discovered association rules”. In Proc. DASFAA 1997, pp. 185-194.
- J. Han, J. Pei, and Y. Yin , “Mining Frequent Patterns without Candidate Generation”. In Proc. of SIGMOD 2000,pp.1-12
Index Terms
Keywords