Mining frequent itemsets with partial enumeration

ABSTRACT

In this paper, we present an algorithm of mining frequent itemsets using partial enumeration and the FP-growth function with reduced depth of recursion. The experimental results show that our algorithm outperforms the original FP-growth algorithm without partial enumeration for the databases with high density.

REFERENCES

• 1: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 2: G. Grahne and J. Zhu. Efficiently using prefix-trees in mining frequent itemsets. In Proceedings of the IEEE ICDM Workshop on Frequent Itemset, 2003.
• 3: Yin-Ling Cheung , Ada Wai-Chee Fu, Mining Frequent Itemsets without Support Threshold: With and without Item Constraints, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1052-1069, September 2004 [doi>10.1109/TKDE.2004.44]
• 4: Peiyi Tang and Markus P. Turkia. Parallelizing frequent itemset mining with FP-trees. To appear in Proceedings of the the 21st 2006 International Conference on Computers and Their Applications (CATA '06), March 2006.
• 5: Peiyi Tang , Li Ning , Ningning Wu, Domain and data partitioning for parallel mining of frequent closed itemsets, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia [doi>10.1145/1167350.1167423]
• 6: Bart Goethals and Mohammed J. Zaki. FIMI'03: Workshop on frequent itemset mininig implementations. Technical report, http://fimi.cs.helsinki.fi/, 2003.
• 7: Peiyi Tang and Markus P. Turkia. Mining frequent itemsets with partial enumeration. Technical Report titus.compsci.ualr.edu/~ptang/papers/partial.pdf, Department of Computer Science, University of Arkansas at Little Rock, 2005.
• 8: Peiyi Tang and Markus P. Turkia. Parallelizing frequent itemset mining with FP-trees. Technical Report titus.compsci.ualr.edu/~ptang/papers/par-fi.pdf, Department of Computer Science, University of Arkansas at Little Rock, 2005.
• 9: Yin ling Cheung. FP-tree/FP-growth: Mining large itemsets using FP-tree algorithm. Technical Report www.cse.cuhk.edu.hk/~kdd/freq/Nmost/ftp.zip, Chinese University of Hong Kong, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Recursion

General Terms:
Performance

Keywords:
k-prefix partitioning, conditional databases, frequent itemsets, partial enumeration