Parallelizing the Count-Min Sketch Algorithm on the Multi-core Processors

ZHANG Yu

Chinese︱Feedback︱Save this page

• Elaborating Academic Views 　　　　 • Exchanging Innovative Ideas
• Protecting Intellectual Properties 　　• Fast Sharing Science Papers

Sponsored by the Center for Science and Technology Development of the Ministry of Education
Supervised by Ministry of Education of the People's Republic of China

Home > Papers

Parallelizing the Count-Min Sketch Algorithm on the Multi-core Processors

ZHANG Yu * #

College of Computer and Control Engineering, Nankai University, 300071

*Correspondence author

#Submitted by

Subject:

Funding: Doctoral Fund of Ministry of Education of China Grant （No.No. 2011031120030）

Opened online:21 December 2015

Accepted by: none

Citation: ZHANG Yu.Parallelizing the Count-Min Sketch Algorithm on the Multi-core Processors[OL]. [21 December 2015] http://en.paper.edu.cn/en_releasepaper/content/4668107

In high-speed network monitoring, the ever-growing traffic calls for a high-performance solution for the computation of items' frequencies. The increasing number of cores in current commodity multi-core processors opens up new opportunities in parallelization. In this paper, we present a novel method that exploits the great parallel capability of multi-cores to speed up the famous Count-Min sketch algorithm. The proposed parallel Count-Min sketch algorithm equally distributes the input data stream into sub-threads which use the original Count-Min sketch algorithm to process the sub-streams. The counters in each local Count-Min sketch with frequency increments exceeding a pre-defined threshold are sent to a merging thread which is able to return the estimated frequencies satisfying the (epsilon, delta)-approximation requirement. The theoretical correctness and complexity analyses are presented. Experiments with real traffic traces confirm the theoretical analyses and demonstrate the excellent performance as well as the effects of parameters. The results show that the proposed parallel Count-Min sketch algorithm achieves near-linear speedup at the cost of greater memory use.

Keywords:Count-Min sketch; Parallel algorithms; Data streams

For this paper

● PDF (0B)
● Revision 0 　　
● Print this paper
● Recommend this paper to a friend
● Add to my favorite list

Saved Papers

Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags

Add yours

Related Papers

Other similar papers
● A Parallel Algorithm for...

Statistics

PDF Downloaded	50
Bookmarked	0
Recommend	0
Comments	Array

Submit your papers

Alert Name:
Alerting to:
Authentication email will be sent to your email address in 24 hours
Frequency:
Email Message Format:	Plain text Graphical(HTML)

Complete the form below and we will recommend the selected titles to your friends on your behalf. * Indicates a required field.
Your name*:
Your email address*:
Recipient's name*:
Recipient's email address*:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find the page(s) useful.

Your name:
Your email address:
Recipient's name:
Recipient's email address:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find this page useful.

Disclaimer: This message was sent to your friend using the "Send it to a friend" facility on the Sciencepaper Online’ WWW site, http://www.paper.edu.cn/en. The Sciencepaper Online is not responsible for the content of this email, and anything said in this email does not necessarily reflect the Sciencepaper Online's views.

	Check out RSS, or use RSS reader to subscribe this item

Saved Papers