Variable-grain and dynamic work generation for minimal unique itemset mining

Paraskevas Yiapanis, David J. Haglin, Anna M. Manning, Ken Mayes, John Keane

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

SUDA2 is a recursive search algorithm for Minimal Unique Itemset detection. Such sets of items are formed via combinations of non-obvious attributes enabling individual record identification. The nature of SUDA2 allows work to be divided into non-overlapping tasks enabling parallel execution. Earlier work developed a parallel implementation for SUDA2 on an SMP cluster, and this was found to be several orders of magnitude faster than sequential SUDA2. However, if fixed-granularity parallel tasks are scheduled naively in the order of their generation, the system load tends to be imbalanced with little work at the beginning and end of the search. This paper investigates the effectiveness of variable-grained and dynamic work generation strategies for parallel SUDA2. These methods restrict the number of sub-tasks to be generated, based on the criterion of probable work size. The further we descend in the search recursion tree, the smaller the tasks become, thus we only select the largest tasks at each level of recursion as being suitable for scheduling. The revised algorithm runs approximately twice as fast as the existing parallel SUDA2 for finer levels of granularity when variable-grained work generation is applied. The dynamic method, performing level-wise task selection based on size, outperforms the other techniques investigated. © 2008 IEEE.
Original languageEnglish
Title of host publicationProceedings - IEEE International Conference on Cluster Computing, ICCC|Proc. IEEE Int. Conf. Cluster Comput. ICCC
PublisherIEEE
Pages33-41
Number of pages8
ISBN (Print)9781424426409
DOIs
Publication statusPublished - 2008
Event2008 IEEE International Conference on Cluster Computing, CCGRID 2008 - Tsukuba
Duration: 1 Jul 2008 → …

Conference

Conference2008 IEEE International Conference on Cluster Computing, CCGRID 2008
CityTsukuba
Period1/07/08 → …

Keywords

  • Computer Science, Hardware & Architecture
  • Engineering, Electrical &
  • Electronic

Fingerprint

Dive into the research topics of 'Variable-grain and dynamic work generation for minimal unique itemset mining'. Together they form a unique fingerprint.

Cite this