|Mining Association Rules with Systolic Trees
|Sun, S., and J. Zambreno
|Proceedings of the International Conference on Field-Programmable Logic and its Applications (FPL)
Association Rules Mining (ARM) algorithms are designed to ﬁnd sets of frequently occurring items in large databases. ARM applications have found their way into a variety of ﬁelds, including medicine, biotechnology, and marketing. This class of algorithm is typically very memory intensive, leading to prohibitive runtimes on large databases. Previous attempts at acceleration using custom or reconﬁgurable hardware have been limited, as many of the signiﬁcant ARM algorithms were designed from a software developer’s perspective and have features (e.g. dynamic linked lists, recursion) that do not translate well to hardware. In this paper we look at how we can accomplish the goal of association rules mining from a hardware perspective. We investigate a popular tree-based ARM algorithm (FP-growth), and make use of a systolic tree structure, which mimics the internal memory layout of the original software algorithm while achieving much higher throughput. Our experimental prototype demonstrates how we can trade memory resources on a software platform for computational resources on a reconﬁgurable hardware platform, in order to exploit a ﬁne-grained parallelism that was not inherent in the original ARM algorithm.