High-utility itemset mining (HUIM) is an important data analytics problem used to identify itemsets that yield high-utility in transactional datasets. Most existing HUIM algorithms are designed for CPUs, operating either sequentially or with limited parallelism. Consequently, they do not exploit the massive data-parallel processing capabilities of modern GPUs. This paper introduces GA-HUIM (GPU-friendly Adaptive-allocation High-Utility Itemset Mining), a novel framework that efficiently maps HUIM workloads to GPU architectures through adaptive compute resource allocation. GA-HUIM employs a level-wise exploration of the itemset lattice, decomposing the search space into independent tasks. Tasks are categorized as large or small based on workload characteristics, enabling differentiated parallelization strategies: large tasks leverage GPU thread-block parallelism with optimized thread allocation, while small tasks are efficiently processed using a highly parallel, one-task-per-thread strategy. A key strategy is our adaptive thread-block sizing, which tunes execution granularity using workload histograms to match the evolving computational demands. Intensive experiments demonstrate that GA-HUIM achieves up to 94.7 times speedup over state-of-the-art CPU approaches and reduces response times by up to 30.7 times compared to static GPU configurations, confirming its effectiveness for GPU-accelerated high-utility pattern discovery.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Adaptive GPU Compute Resource Allocation for Efficient High-Utility Itemset Mining

  • Tarun Sreepada,
  • Tsuyoshi Ozawa,
  • Genki Kimura,
  • Uday Rage Kiran,
  • Kazuo Goda

摘要

High-utility itemset mining (HUIM) is an important data analytics problem used to identify itemsets that yield high-utility in transactional datasets. Most existing HUIM algorithms are designed for CPUs, operating either sequentially or with limited parallelism. Consequently, they do not exploit the massive data-parallel processing capabilities of modern GPUs. This paper introduces GA-HUIM (GPU-friendly Adaptive-allocation High-Utility Itemset Mining), a novel framework that efficiently maps HUIM workloads to GPU architectures through adaptive compute resource allocation. GA-HUIM employs a level-wise exploration of the itemset lattice, decomposing the search space into independent tasks. Tasks are categorized as large or small based on workload characteristics, enabling differentiated parallelization strategies: large tasks leverage GPU thread-block parallelism with optimized thread allocation, while small tasks are efficiently processed using a highly parallel, one-task-per-thread strategy. A key strategy is our adaptive thread-block sizing, which tunes execution granularity using workload histograms to match the evolving computational demands. Intensive experiments demonstrate that GA-HUIM achieves up to 94.7 times speedup over state-of-the-art CPU approaches and reduces response times by up to 30.7 times compared to static GPU configurations, confirming its effectiveness for GPU-accelerated high-utility pattern discovery.