Efficient Frequent Item Counting in Multi-Core Hardware
Publication Details
Title
Efficient Frequent Item Counting in Multi-Core Hardware
Authors
Pratanu Roy, Jens Teubner, and Gustavo Alonso
Published
Proceedings of the 2012 ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2012), Beijing, China, August 2012.
Download
Abstract
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.
Publication Log
May 2012
camera-ready for KDD 2012
February 2012
submission to KDD 2012 (accepted)
- submission (PDF)
- reviews (results: “I will argue to accept”, “Leave for senior PC to decide”, “Leave for senior PC to decide”)
December 2011
submission to (P)VLDB 2012 (rejected)
- submission (PDF)
- reviews (results: reject, reject, reject)