Association Rule Mining with the Micron Automata Processor
Association Rule Mining with the Micron Automata Processor
复制标题
DOI：
10.1109/ipdps.2015.101
复制
发表时间：
2015-05
期刊：
影响因子：
--
通讯作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
中科院分区：
文献类型：
--
作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
关联规则挖掘（ARM）是一种广泛使用的数据挖掘技术，用于发现大型数据库中频繁关联的项目集。随着数据集规模的增长和实时分析变得重要，ARM实现的性能可能会阻碍其适用性。我们通过使用Micron的自动机处理器（AP）来加速ARM，AP是一种非确定性有限自动机（NFA）的硬件实现，其附加功能大大扩展了AP的功能，超越了传统NFA的功能。ARM用于发现项目集的Apriori算法自然映射到AP的大规模并行性。我们通过AP的符号替换功能（一种轻量级的可重构性）实现了Apriori ARM中使用的多遍剪枝策略。与Apriori单核CPU实现和Eclat（一种更高效的ARM算法）6核多进程CPU实现相比，AP加速Apriori在7个合成数据集和真实数据集上分别实现了129倍和49倍的加速比。AP加速的Apriori解决方案也优于Eclat的GPU实现，特别是对于大型数据集。技术扩展预测表明，未来几代AP将有更好的加速。
Association rule mining (ARM) is a widely used data mining technique for discovering sets of frequently associated items in large databases. As datasets grow in size and real-time analysis becomes important, the performance of ARM implementation can impede its applicability. We accelerate ARM by using Micron's Automata Processor (AP), a hardware implementation of non-deterministic finite automata (NFAs), with additional features that significantly expand the APs capabilities beyond those of traditional NFAs. The Apriori algorithm that ARM uses for discovering item sets maps naturally to the massive parallelism of the AP. We implement the multipass pruning strategy used in the Apriori ARM through the APs symbol replacement capability, a form of lightweight reconfigurability. Up to 129X and 49X speedups are achieved by the AP-accelerated Apriori on seven synthetic and real-world datasets, when compared with the Apriori single-core CPU implementation and Eclat, a more efficient ARM algorithm, 6-core multicourse CPU implementation, respectively. The AP-accelerated Apriori solution also outperforms GPU implementations of Eclat especially for large datasets. Technology scaling projections suggest even better speedups from future generations of AP.