A Frequency-aware Parallel Algorithm for Counting Stream Items on Multicore Processors

We present a parallel counting algorithm for estimating frequencies of items from data streams where a stream is ingested and queried in parallel by partitioning data over multiple processing cores of a multi-core processor. We demonstrate that current probabilistic counting algorithms are ill-suited to be used as the sequential kernel in the parallel algorithm due to space limitations, inaccuracies in approximating counts of low frequency items, and inability to identify the absent items in a stream. To address these concerns, we have devised a new sequential counting algorithm, called the Frequency-aware Counting Algorithm (FCM). FCM is related to the Cormode-Muthukrishnan Count-Min algorithm and incorporates novel capabilities for improving accuracy in estimating low-frequency items by dynamically capturing frequency changes of items in the stream, and using a variable number of hash functions per item as determined by an item’s current frequency. FCM also uses an auxiliary space-efficient data structure to reduce the errors due to absent items.

We have implemented the parallel counting algorithm on the multi-core Cell processor using the FCM algorithm as the sequential kernel. We experimentally and analytically demonstrate that with similar space consumption, FCM computes better frequency estimates of both the low- and high-frequency items than the Count-Min algorithm by reducing collisions with high-frequency items. FCM also significantly reduces the errors in identifying absent items. In the parallel scenario, as the number of processing cores is increased, using a hash-based data partitioning approach, our parallel algorithm is able to scale the overall performance linearly as well as improve the estimate accuracy.