Jump label

Service navigation

Main navigation

You are here:

Main content

Efficient Frequent Item Counting in Multi-Core Hardware

Publication Details


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.


paper (PDF)


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)

Sub content


Prof. Dr. Jens Teubner
Tel.: 0231 755-6481