Cilk++ Multicore FP-Tree Pattern Mining Algorithm

Yuxiong He has posted a great look at multicore parallelization of the FP-tree algorithm for frequent pattern mining via the Cilkarts blog.  Naturally, the example provides a Cilk++ sample implementation of the algorithm and associated performance metrics.  The article is quite detailed and presents some great code examples (we love code at insideHPC).

The FP-tree algorithm builds a prefix tree representation of a given database of transactions, and generates a complete group of frequent item sets through recursive tree projections.

Without stealing too much of He’s thunder, his Cilk++ implementation results in a 3.6X speedup on tree building and a 6.6X speedup on frequent set generation using a 16core AMD Opeteron machine.