Efficient Parallel Mining of High-utility Itemsets on Multicore Processors
Efficient Parallel Mining of High-utility Itemsets on Multicore Processors
复制标题
DOI：
10.1109/icde55515.2023.00384
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Genki Kimura;Yuto Hayamizu;R. U. Kiran;Masaru Kitsuregawa;K. Goda
中科院分区：
文献类型：
--
作者：
Genki Kimura;Yuto Hayamizu;R. U. Kiran;Masaru Kitsuregawa;K. Goda
高效用项集挖掘是著名的频繁项集挖掘的一个推广问题，它不仅考虑出现的频率，而且还考虑定量的标准，如单位利润。因为它可以应用于更广泛的知识发现工作，在过去的二十年中，各种算法的改进已经被研究。另一方面，尽管硬件趋势发生了重大变化，但在利用硬件性能方面所做的努力有限。本文提出了一种新的并行化方法DPHIM（动态并行化的高效用项目集挖掘）。DPHIM动态地将高效用项集挖掘的执行分解为子任务以利用逻辑数据并行性，并以NUMA感知的方式将子任务及其相关数据仔细地分配给物理资源，例如处理核心和附近的存储器。我们密集和广泛的实验已经证实，DPHIM的执行速度比完全调优的串行执行快65.23倍，比静态分区快23.54倍，比DRAM上各种数据集和配置的替代动态并行执行的最佳情况快2.51倍。同样，我们已经证明了DPHIM在持久内存上有效地工作;它提供了类似的线程可伸缩性趋势，并且在持久内存上慢1.07到2.43倍。
High-utility itemset mining is a generalized problem of well-known frequent itemset mining, which considers not only the frequency of occurrence but also quantitative criteria such as unit profit. Because it can be applied to a wider spectrum of knowledge discovery work, various algorithmic improvements have been studied over the past two decades. On the other hand, limited efforts have been made to take advantage of hardware performance despite significant changes in hardware trends. This paper presents a novel parallelization method called DPHIM (Dynamic Parallelization for High-utility Itemset Mining). DPHIM dynamically decomposes the execution of high-utility itemset mining into subtasks in order to leverage logical data parallelism, and carefully assigns the subtasks and their related data to physical resources such as processing cores and nearby memory in the NUMA-aware manner. Our intensive and extensive experiments have confirmed that DPHIM performs up to 65.23 times faster than the fully-tuned serial execution, up to 23.54 times faster than static partitioning, and up to 2.51 times faster than the best case of alternative dynamic parallel executions for a variety of datasets and configurations on DRAM. As well, we have demonstrated that DPHIM effectively worked on persistent memory; it offered similar thread scalability trends and was 1.07 to 2.43 times slower on persistent memory.