Out-of-core frequent pattern mining on a commodity PC

ABSTRACT

In this work we focus on the problem of frequent itemset mining on large, out-of-core data sets. After presenting a characterization of existing out-of-core frequent itemset mining algorithms and their drawbacks, we introduce our efficient, highly scalable solution. Presented in the context of the FPGrowth algorithm, our technique involves several novel I/O-conscious optimizations, such as approximate hash-based sorting and blocking, and leverages recent architectural advancements in commodity computers, such as 64-bit processing. We evaluate the proposed optimizations on truly large data sets,up to 75GB, and show they yield greater than a 400-fold execution time improvement. Finally, we discuss the impact of this research in the context of other pattern mining challenges, such as sequence mining and graph mining.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, 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: Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle, Managing energy and server resources in hosting centers, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 6: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 7: Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, Cache-conscious frequent pattern mining on a modern processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: B. Goethals and M. Zaki. Advances in frequent itemset mining implementations. In Proceedings of the ICDM workshop on frequent itemset mining implementations, 2003.
• 9: Karam Gouda , Mohammed Javeed Zaki, Efficiently Mining Maximal Frequent Itemsets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.163-170, November 29-December 02, 2001
• 10: G. Grahne and J. Zhu. Efficiently using prefix-trees in mining frequent itemsets. In Proceedings of the ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
• 11: Gosta Grahne , Jianfei Zhu, Mining Frequent Itemsets from Secondary Memory, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.91-98, November 01-04, 2004
• 12: 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
• 13: G. Liu, H. Lu, J. X. Yu, W. Wei, and X. Xiao. Afopt: An efficient implementation of pattern growth approach. In Proceedings of the ICDM workshop on frequent itemset mining implementations, 2003.
• 14: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 15: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 16: S. Parthasarathy, M. Zaki, M. Ogihara, and W. Li. Memory placement techniques for parallel association mining. International Conference on Knowledge Discovery and Data Mining (SIGKDD), 1998.
• 17: S. Parthasarathy , M. J. Zaki , M. Ogihara , W. Li, Parallel data mining for association rules on shared memory systems, Knowledge and Information Systems, v.3 n.1, p.1-29, February 2001 [doi>10.1007/PL00011656]
• 18: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 19: Craig Silverstein , Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman, Scalable Techniques for Mining Causal Structures, Proceedings of the 24rd International Conference on Very Large Data Bases, p.594-605, August 24-27, 1998
• 20: M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery discovery of association rules. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), 1995.
• 21: Jingren Zhou , John Cieslewicz , Kenneth A. Ross , Mihir Shah, Improving database performance on simultaneous multithreading processors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
data mining, itemsets, out of core, pattern mining, secondary memory