Factors affecting the performance of parallel mining of minimal unique itemsets on diverse architectures

D. J. Haglin, Kenneth Mayes, Anna Manning, J. Feo, J. R. Gurd, M. Elliot, J. A. Keane

Research output: Contribution to journalArticlepeer-review

Abstract

Three parallel implementations of a divide-and-conquer search algorithm (called SUDA2) for finding minimal unique itemsets (MUIs) are compared in this paper. The identification of MUIs is used by national statistics agencies for statistical disclosure assessment. The first parallel implementation adapts SUDA2 to a symmetric multi-processor cluster using the message passing interface (MPI), which we call an MPI cluster; the second optimizes the code for the Cray MTA2 (a shared-memory, multi-threaded architecture) and the third uses a heterogeneous 'group' of workstations connected by LAN. Each implementation considers the parallel structure of SUDA2, and how the subsearch computation times and sequence of subsearches affect load balancing. All three approaches scale with the number of processors, enabling SUDA2 to handle larger problems than before. For example, the MPI implementation is able to achieve nearly two orders of magnitude improvement with 132 processors. Performance results are given for a number of data sets. © 2009 John Wiley & Sons, Ltd.
Original languageEnglish
Pages (from-to)1131-1158
Number of pages27
JournalConcurrency and Computation: Practice & Experience
Volume21
Issue number9
DOIs
Publication statusPublished - 25 Jun 2009

Keywords

  • Divide-and-conquer algorithm
  • Itemset mining
  • Load balancing
  • Parallel architecture
  • Performance

Fingerprint

Dive into the research topics of 'Factors affecting the performance of parallel mining of minimal unique itemsets on diverse architectures'. Together they form a unique fingerprint.

Cite this