Parallel Hardware Architecture for Mining Association Rules
Date Issued
2006
Date
2006
Author(s)
Wen, Ying-Hsiang
DOI
en-US
Abstract
Generally speaking, to implement Apriori-based association rule mining in hardware, one has to load candidate itemsets and a database into the hardware. Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets or the number of items in the database is larger than the hardware capacity, the items are loaded into the hardware separately. The time complexity is in proportion to the number of candidate
itemsets multiplied by the number of items in the database. Too many candidate itemsets and a large database would create a performance bottleneck. In this thesis, we propose a HAsh-based and PiPelIned architecture (abbreviated as HAPPI) for hardware-enhanced association rule mining. We apply the pipeline methodology in the HAPPI architecture to compare itemsets with the database and collect useful information for reducing the number
of candidate itemsets and items in the database simultaneously. When the database is fed into the hardware, candidate itemsets are compared with the items in the database to find frequent itemsets. At the same time, trimming information is collected from each
transaction. In addition, itemsets are generated from transactions and hashed into a hash table. The useful trimming information and the hash table enable us to reduce the number of items in the database and the number of candidate itemsets. Therefore, we can effectively reduce the frequency of loading the database into the hardware. As such, HAPPI solves the bottleneck problem in Apriori-based hardware schemes. We also derive some properties to investigate the performance of this hardware implementation. As shown by the experiment results, HAPPI significantly outperforms the previous hardware approach in terms of execution cycles.
Subjects
資料探勘
關聯性規則
硬體加速
心縮陣列
管線化
可程式化邏輯閘陣列
data mining
association rules
hardware-enhanced
systolic array
pipeline
FPGA
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93921043-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):bd6892f23175cd8c331f4b2258c65f3d