SC14 New Orleans, LA

The International Conference for High Performance Computing, Networking, Storage and Analysis

Association Rule Mining with the Micron Automata Processor.

Authors: Ke Wang (University of Virginia), Mircea Stan (University of Virginia), Kevin Skadron (University of Virginia)

Abstract: Association rule mining (ARM) is a widely used data mining technique for discovering sets of frequently associated items in large databases. As datasets grow in size and real-time analysis becomes important, the performance of ARM implementation can impede its applicability. We accelerate ARM by using Micron's Automata Processor (AP), a hardware implementation of non-deterministic finite automata (NFAs), with additional features that significantly expand the AP’s capabilities beyond those of traditional NFAs. The Apriori algorithm that ARM uses for discovering itemsets maps naturally to the massive parallelism of the AP. We implement the multipass pruning strategy of Apriori through AP’s symbol replacement capability, a form of lightweight reconfigurability. 87-95X speedups are achieved by the AP-accelerated Apriori on synthetic and real-world datasets respectively, when compared with the Apriori single-core CPU implementation. The AP-accelerated Apriori solution also outperforms multicore and GPU implementations of Eclat, a more efficient ARM algorithm, especially for large datasets.

Poster: pdf
Two-page extended abstract: pdf

Poster Index