Mining association rules with systolic trees

Association Rules Mining (ARM) algorithms are designed to find sets of frequently occurring items in large databases. ARM applications have found their way into a variety of fields, including medicine, biotechnology, and marketing. This class of algorithm is typically very memory intensive, leading to prohibitive runtimes on large databases. Previ-ous attempts at acceleration using custom or reconfigurable hardware have been limited, as many of the significant ARM algorithms were designed from a software developer’s per-spective and have features (e.g. dynamic linked lists, recur-sion) 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 pop-ular tree-based ARM algorithm (FP-growth), and make use of a systolic tree structure, which mimics the internal mem-ory layout of the original software algorithm while achiev-ing much higher throughput. Our experimental prototype demonstrates how we can trade memory resources on a soft-ware platform for computational resources on a reconfig-urable hardware platform, in order to exploit a fine-grained parallelism that was not inherent in the original ARM algo-rithm. 1