An FPGA-Based Accelerator for Frequent Itemset Mining

作者：Zhang Yan^*; Zhang Fan; Jin Zheming; Bakos Jason D

来源：ACM Transactions on Reconfigurable Technology and Systems, 2013, 6(1): 2.

DOI：10.1145/2457443.2457445

• Performance
• Frequent itemset mining
• data mining
• Eclat
• data intensive
• co-processor
• high performance computing
• reconfigurable applications
• reconfigurable

In this article we describe a Field Programmable Gate Array (FPGA)-based coprocessor architecture for Frequent Itemset Mining (FIM). FIM is a common data mining task used to find frequently occurring subsets amongst a database of sets. FIM is a nonnumerical, data intensive computation and is used in machine learning and computational biology. FIM is particularly expensive-in terms of execution time and memory-when performed on large and/or sparse databases or when applied using a low appearance frequency threshold. Because of this, the development of increasingly efficient FIM algorithms and their mapping to parallel architectures is an active field. Previous attempts to accelerate FIM using FPGAs have relied on performance-limiting strategies such as iterative database loading and runtime logic unit reconfiguration. In this article, we present a novel architecture to implement Eclat, a well-known FIM algorithm. Unlike previous efforts, our technique does not impose limits on the maximum set size as a function of available FPGA logic resources and our design scales well to multiple FPGAs. In addition to a novel hardware design, we also present a corresponding compression scheme for intermediate results that are stored in on-chip memory. On a four-FPGA board, experimental results show up to 68X speedup compared to a highly optimized software implementation.

• 出版日期2013-5