Efficient pattern mining on shared memory systems: implications for chip multiprocessor architectures

ABSTRACT

Frequent pattern mining is a fundamental data mining process which has practical applications ranging from market basket data analysis to web link analysis. In this work, we show that state-of-the-art frequent pattern mining applications are inefficient when executing on a shared memory multiprocessor system, due primarily to poor utilization of the memory hierarchy. To improve the efficiency of these applications, we explore memory performance improvements, task partitioning strategies, and task queuing models designed to maximize the scalability of pattern mining on SMP systems. Empirically, we show that the proposed strategies afford significantly improved performance. We also discuss implications of this work in light of recent trends in micro-architecture design, particularly chip multiprocessors (CMPs).

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 , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996 [doi>10.1109/69.553164]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States
• 5: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.51, December 09-12, 2002
• 6: 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
• 7: Julia Chen , Philo Juang , Kevin Ko , Gilberto Contreras , David Penry , Ram Rangan , Adam Stoler , Li-Shiuan Peh , Margaret Martonosi, Hardware-modulated parallelism in chip multiprocessors, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105742]
• 8: Y. Chen, L. Yang, and Y. Wang. Incremental mining of frequent xml query patterns. In Proceedings of the International Conference on Data Mining (ICDM), 1999.
• 9: Shengnan Cong , Jiawei Han , Jay Hoeflinger , David Padua, A sampling-based framework for parallel data mining, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065979]
• 10: Diane J. Cook , Lawrence B. Holder , Gehad Galal , Ron Maglothin, Approaches to parallel graph-based knowledge discovery, Journal of Parallel and Distributed Computing, v.61 n.3, p.427-446, March 1, 2001 [doi>10.1006/jpdc.2000.1696]
• 11: L. Dehaspe, H. Toivonen, and R. D. King. Finding frequent substructures in chemical compounds. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, pages 30--36. AAAI Press, 1998.
• 12: 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
• 13: A. Ghoting, G. Buehrer, S. Parthasarathy, D. Kim, A. Nguyen, Y. Chen, and P. Dubey. Cache-conscious frequent pattern mining on modern and emerging architectures. In OSU Technical Report, volume OSU-CISRC-3/06-TR31, 2006.
• 14: B. Goethals and M. Zaki. Advances in frequent itemset mining implementations. In Proceedings of the ICDM workshop on frequent itemset mining implementations, 2003.
• 15: 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
• 16: V. Guralnik and G. Karypis. Dynamic load balancing algorithms for sequence mining. In University of Minnesota Technical Report TR 00-056, 2001.
• 17: Eui-Hong (Sam) Han , George Karypis , Vipin Kumar, Scalable Parallel Data Mining for Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.337-352, May 2000 [doi>10.1109/69.846289]
• 18: 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
• 19: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 20: E. P. Markatos , T. J. LeBlanc, Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.379-400, April 1994 [doi>10.1109/71.273046]
• 21: B. McKay. Practical graph isomorphism. In Congressus Numerantium, volume 30, pages 45--87, 1981.
• 22: T. Meinl, I. Fischer, and M. Philippsen. Parallel mining for frequent fragments on a shared-memory multiprocessor -results and java-obstacles-. In LWA 2005 - Beitrge zur GI-Workshopwoche Lernen, Wissensentdeckung, Adaptivitt, pages 196--201, Saarbrcken, Germany, 2005.
• 23: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014134]
• 24: 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
• 25: Srinivasan Parthasarathy , Sandhya Dwarkadas , Mitsunori Ogihara, Active data mining in a distributed setting, 2000
• 26: Srinivasan Parthasarathy , Matt Coatney, Efficient Discovery of Common Substructures in Macromolecules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.362, December 09-12, 2002
• 27: 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]
• 28: 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]
• 29: John R. Punin , Mukkai S. Krishnamoorthy , Mohammed Javeed Zaki, LOGML: Log Markup Language for Web Usage Mining, Revised Papers from the Third International Workshop on Mining Web Log Data Across All Customers Touch Points, p.88-112, August 26, 2001
• 30: Chao Wang , Srinivasan Parthasarathy, Parallel algorithms for mining frequent structural motifs in scientific data, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006215]
• 31: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 32: Mohammed J. Zaki, Parallel sequence mining on shared-memory machines, Journal of Parallel and Distributed Computing, v.61 n.3, p.401-426, March 1, 2001 [doi>10.1006/jpdc.2000.1695]
• 33: M. Zaki and C. Hsiao. CHARM: An efficient algorithm for closed itemset mining. In Proceedings of SIAM International Conference on Data Mining (SDM), 2002.
• 34: M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. pages 283--296, 1997.
• 35: Mohammed J. Zaki , Vinay Nadimpally , Deb Bardhan , Chris Bystroff, Predicting protein folding pathways, Bioinformatics, v.20 n.1, p.386-393, January 2004 [doi>10.1093/bioinformatics/bth935]

INDEX TERMS

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

General Terms:
Algorithms, Performance