On the design of hardware architectures for parallel frequent itemsets mining

摘要

Algorithms for Frequent Itemsets Mining have proved their effectiveness for extracting frequent sets of patterns in datasets. However, in some specific cases, they do not obtain the expected results in an acceptable time. For this reason, Field Programmable Gates Array-based architectures for Frequent Itemsets Mining have been proposed to accelerate this task. The current paper proposes a search strategy for Frequent Itemsets Mining based on equivalence classes partitioning. The partitioning on equivalence classes allows dividing the search space into disjoint sets that can be processed in parallel. Consequently, this paper presents the design and implementation of two hardware architectures that exploit the nested parallelism in the proposed search strategy. These hardware architectures are capable of obtaining frequent itemsets regardless of the number of distinct items and the number of transactions in the dataset, which are the main issues reported in the reviewed literature. Furthermore, the proposed architectures explore the trade-off between acceleration and hardware resource utilization. The experimental results obtained demonstrate that the proposed search strategy can be scaled to achieve a speedup in the processing time of 40 times faster than software-based implementations. (C) 2020 Elsevier Ltd. All rights reserved.