Parallel data mining for association rules on shared-memory multi-processors

ABSTRACT

Data mining is an emerging research area, whose goal is to extract significant patterns or interesting rules from large databases. High-level inference from large volumes of routine business data can provide valuable information to businesses, such as customer buying patterns, shelving criterion in supermarkets and stock trends. Many algorithms have been proposed for data mining of association rules. However, research so far has mainly focused on sequential algorithms. In this paper we present parallel algorithms for data mining of association rules, and study the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor. We further present a set of optimizations for the sequential and parallel algorithms.Experiments show that a significant improvement of performance is achieved using our proposed optimizations. We also achieved good speed-up for the parallel algorithm, but we observe a need for parallel I/O techniques for further performance gains.

REFERENCES

• 1: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 2: 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
• 3: Rakesh Agrawal , Hiekki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 4: R. Agrawal and J. Shafer. Parallel mining of association rules: design, implementation, and experience. Technical Report RJ10004, IBM Almaden Research Center, San Jose, CA 95120, Jan. 1996.
• 5: 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
• 6: M. Cierniak , Wei Li , M. J. Zaki, Loop scheduling for heterogeneity, Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing - HPDC '95, p.78, August 02-04, 1995
• 7: M. Holsheimer, M. Kersten, H. Mannila, and H. Toivonen. A perspective on databases and data mining. In 1st Intl. Conf. Knowledge Discovery and Data Mining, Aug. 1995.
• 8: M. Houtsma and A. Swami. Set-oriented mining of association rules. In RJ 9567. IBM Almaden, Oct. 1993.
• 9: H. Mannila, H. Toivonen, and I. Verkamo. Efficient algorithms for discovering association rules. In AAAI Wkshp. Knowledge Discovery in Databases, July 1994.
• 10: 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
• 11: J. S. Park, M. Chen, and P. S. Yu. Efficient parallel data mining for association rules. Technical Report RC20156, IBM T. J. Watson Research Center, Aug. 1995.
• 12: G. Piatetsky-Shapiro. Discovery, presentation and analysis of strong rules. In G. P.-S. et al, editor, KDD. AAAI Press, 1991.
• 13: 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
• 14: Mohammed J Zaki , Mitsunori Ogihara , Srinivasan Parthasarathy , Wei Li, Parallel Data Mining for Association Rules on Shared-Memory Multiprocessors, University of Rochester, Rochester, NY, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Management, Performance, Theory

Keywords:
Data Mining, Association Rules, Load Balancing, Hash Tree Balancing, Hashing, Shared-Memory Multi-processor