Parallel data mining for association rules on shared-memory systems

DOI10.1007/PL00011656MaRDI QIDQ1606541zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 25 July 2002

Published in Knowledge and Information Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00011656

zbMATH Keywords

Association rulesImproving localityMemory placementParallel data miningReducing false sharing

Mathematics Subject Classification ID

Database theory (68P15) Information storage and retrieval of data (68P20) Computing methodologies and applications (68U99)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1869808
• Parallel sequence mining on shared-memory machines
• scientific article; zbMATH DE number 1700011
• An efficient parallel algorithm for mining association rules
• scientific article; zbMATH DE number 1863282

Cited in

(10)

• Representing a concept lattice by a graph
• Parallel extraction of association rules from genomics data
• Widening: using parallel resources to improve model quality
• scientific article; zbMATH DE number 1700011 (Why is no real title available?)
• Parallel Associative Classification Data Mining Frameworks Based MapReduce
• scientific article; zbMATH DE number 1869808 (Why is no real title available?)
• scientific article; zbMATH DE number 2090604 (Why is no real title available?)
• scientific article; zbMATH DE number 2221092 (Why is no real title available?)
• Characterization and parallelization of decision-tree induction
• Parallel sequence mining on shared-memory machines

This page was built for publication: Parallel data mining for association rules on shared-memory systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606541)