CFP last date
22 April 2024
Reseach Article

Batch Processing for Incremental FP-tree Construction

by PVGD Prasad Reddy, Geeta R. B., Shashikumar G. Totad
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

@article{ 10.5120/910-1288,
author = { PVGD Prasad Reddy, Geeta R. B., Shashikumar G. Totad },
title = { Batch Processing for Incremental FP-tree Construction },
journal = { International Journal of Computer Applications },
issue_date = { August 2010 },
volume = { 5 },
number = { 5 },
month = { August },
year = { 2010 },
issn = { 0975-8887 },
pages = { 28-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume5/number5/910-1288/ },
doi = { 10.5120/910-1288 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:53:28.683141+05:30
%A PVGD Prasad Reddy
%A Geeta R. B.
%A Shashikumar G. Totad
%T Batch Processing for Incremental FP-tree Construction
%J International Journal of Computer Applications
%@ 0975-8887
%V 5
%N 5
%P 28-32
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. R.J. Bayardo , “Efficient mining of long patterns from databases”. In Proc. SIGMOD 1998, pp. 85-93.
  3. 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.
  4. Agrawal R, Srikant R. “Fast Algorithms for Mining Association Rules”. In Proc. of VLDB, Sep 2- 15 1994, pp. 487-99.
  5. 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.
  6. F. Bonchi and C. Lucchese, “ On closed constrained frequent pattern mining”. In Proc ICDM 2004,pp. 35-42.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. J. Han, J. Pei, and Y. Yin , “Mining Frequent Patterns without Candidate Generation”. In Proc. of SIGMOD 2000,pp.1-12
Index Terms

Computer Science
Information Sciences

Keywords

Batch Incremental Mining Batch Incremental tree Sequential Incremental Mining minSup