Parallel Data Mining for Association Rules on Shared-Memory Systems |
| |
Authors: | S Parthasarathy M J Zaki M Ogihara W Li |
| |
Affiliation: | (1) Department of Computer and Information Sciences, Ohio State University, Columbus, OH, USA, US;(2) Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, USA, US;(3) Department of Computer Science, University of Rochester, Rochester, NY, USA, US;(4) Intel Corporation, Santa Clara, CA, USA, US |
| |
Abstract: | In this paper we present a new parallel algorithm for data mining of association rules on shared-memory multiprocessors.
We study the degree of parallelism, synchronization, and data locality issues, and present optimizations for fast frequency
computation. Experiments show that a significant improvement of performance is achieved using our proposed optimizations.
We also achieved good speed-up for the parallel algorithm.
A lot of data-mining tasks (e.g. association rules, sequential patterns) use complex pointer-based data structures (e.g. hash
trees) that typically suffer from suboptimal data locality. In the multiprocessor case shared access to these data structures may also result in false sharing. For these tasks it is commonly observed that the recursive data structure is built once and accessed multiple times during
each iteration. Furthermore, the access patterns after the build phase are highly ordered. In such cases locality and false
sharing sensitive memory placement of these structures can enhance performance significantly. We evaluate a set of placement
policies for parallel association discovery, and show that simple placement schemes can improve execution time by more than
a factor of two. More complex schemes yield additional gains.
Received 24 May 1999 / Revised 20 June 2000 / Accepted in revised form 6 July 2000 |
| |
Keywords: | : Association rules Improving locality Memory placement Parallel data mining Reducing false sharing |
本文献已被 SpringerLink 等数据库收录! |
|