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.
Linky linky?
Joe – added.