LCM ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining

ABSTRACT

For a transaction database, a frequent itemset is an itemset included in at least a specified number of transactions. To find all the frequent itemsets, the heaviest task is the computation of frequency of each candidate itemset. In the previous studies, there are roughly three data structures and algorithms for the computation: bitmap, prefix tree, and array lists. Each of these has its own advantage and disadvantage with respect to the density of the input database. In this paper, we propose an efficient way to combine these three data structures so that in any case the combination gives the best performance.

REFERENCES

• 1: A. Fiat and S. Shporer, "AIM2: Improved implementation of AIM" In Proc. IEEE ICDM'04 Workshop FIMI'04, 2004.
• 2: B. Racz, "nonordfp: An FP-growth variation without rebuilding the FP-tree," In Proc. IEEE ICDM'04 Workshop FIMI'04, 2004.
• 3: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 4: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 5: D. Burdick, M. Calimlim, J. Flannick, J. Gehrke, and T. Yiu, "MAFIA: A Performance Study of Mining Maximal Frequent Itemsets," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 6: B. Goethals, the FIMI repository, http://fimi.cs.helsinki.fi/, 2003.
• 7: G. Grahne and J. Zhu, "Efficiently Using Prefix-trees in Mining Frequent Itemsets," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 8: 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
• 9: Guimei Liu, Hongjun Lu, Jeffrey Xu Yu, Wang Wei, and Xiangye Xiao, "AFOPT: An Efficient Implementation of Pattern Growth Approach," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 10: S. Orlando, C. Lucchese, P. Palmerini, R. Perego and F. Silvestri, "kDCI: a Multi-Strategy Algorithm for Mining Frequent Sets," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 11: C. Lucchese, S. Orlando and R. Perego, "DCI Closed: A Fast and Memory Efficient Algorithm to Mine Frequent Closed Itemsets," In Proc. IEEE ICDM'04 Workshop FIMI'04, 2004.
• 12: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4]
• 13: A. Pietracaprina and D. Zandolin, "Mining Frequent Itemsets using Patricia Tries," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 14: T. Uno, T. Asai, Y. Uchida, H. Arimura, "LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 15: T. Uno, T. Asai, Y. Uchida, H. Arimura, "An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases," Lecture Notes in Artificial Intelligence 3245, pp. 16--31, 2004.
• 16: T. Uno, M. Kiyomi, H. Arimura, "LCM ver. 2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets", In Proc. IEEE ICDM'04 Workshop FIMI'04, 2004.