Parallel mining algorithms for generalized association rules with classification hierarchy

ABSTRACT

Association rule mining recently attracted strong attention. Usually, the classification hierarchy over the data items is available. Users are interested in generalized association rules that span different levels of the hierarchy, since sometimes more interesting rules can be derived by taking the hierarchy into account. In this paper, we propose the new parallel algorithms for mining association rules with classification hierarchy on a shared-nothing parallel machine to improve its performance. Our algorithms partition the candidate itemsets over the processors, which exploits the aggregate memory of the system effectively. If the candidate itemsets are partitioned without considering classification hierarchy, both the items and its all the ancestor items have to be transmitted, that causes prohibitively large amount of communications. Our method minimizes interprocessor communication by considering the hierarchy. Moreover, in our algorithm, the available memory space is fully utilized by identifying the frequently occurring candidate itemsets and copying them over all the processors, through which frequent itemsets can be processed locally without any communication. Thus it can effectively reduce the load skew among the processors. Several experiments are done by changing the granule of copying itemsets, from the whole tree, to the small group of the frequent itemsets along the hierarchy. The coarser the grain, the easier the control but it is rather difficult to achieve the sufficient load balance. The finer the grain, the more complicated the control is required but it can balance the load quite well. We implemented proposed algorithms on IBM SP-2. Performance evaluations show that our algorithms are effective for handling skew and attain sufficient speedup ratio.

REFERENCES

• AS96: 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]
• CHN+96: David W. Cheung , Jiawei Han , Vincent T. Ng , Ada W. Fu , Yongjian Fu, A fast distributed algorithm for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.31-43, December 18-20, 1996, Miami Beach, Florida, United States
• CNFF96: David W. Cheung , Vincent T. Ng , Ada W. Fu , Yongjian Fu, Efficient Mining of Association Rules in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.911-922, December 1996 [doi>10.1109/69.553158]
• HKK97: Eui-Hong Han , George Karypis , Vipin Kumar, Scalable parallel data mining for association rules, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.277-288, May 11-15, 1997, Tucson, Arizona, United States
• PCY95: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Efficient parallel data mining for association rules, Proceedings of the fourth international conference on Information and knowledge management, p.31-36, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221320]
• RR94: 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
• SA95: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• SA96: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• SK96: Takahiko Shintani , Masaru Kitsuregawa, Hash based parallel algorithms for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.19-30, December 18-20, 1996, Miami Beach, Florida, United States
• SK98: Takahiko Shintani , Masaru Kitsuregawa, Mining Algorithms for Sequential Patterns in Parallel: Hash Based Approach, Proceedings of the Second Pacific-Asia Conference on Research and Development in Knowledge Discovery and Data Mining, p.283-294, April 15-17, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation, Measurement