Efficient Frequent Item Counting in Multi-Core Hardware
Pratanu Roy, Jens Teubner, and Gustavo Alonso
Proceedings of the 2012 ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2012), Beijing, China, August 2012.
The increasing number of cores and the rich instruction sets of modern hardware are opening up new opportunities for optimizing many traditional data mining tasks. In this paper we demonstrate how to speed up the performance of the computation of frequent items by almost one order of magnitude over the best published results by matching the algorithm to the underlying hardware architecture.
We start with the observation that frequent item counting, like other data mining tasks, assumes certain amount of skew in the data. We exploit this skew to design a new algorithm that uses a pre-filtering stage that can be implemented in a highly efficient manner through SIMD instructions. Using pipelining, we then combine this pre-filtering stage with a conventional frequent item algorithm (Space-Saving) that will process the remainder of the data. The resulting operator can be parallelized with a small number of cores, leading to a parallel implementation that does not suffer any of the overheads of existing parallel solutions when querying the results and offers significantly higher throughput.
camera-ready for KDD 2012
submission to KDD 2012 (accepted)
submission to (P)VLDB 2012 (rejected)