An Overview of Count-Min Sketch and its Applications

EasyChair Preprint 879

Abstract

Research into data stream processing algorithms has been going on for over 20 years by now. Its relevance has rapidly grown in recent years, due to advancements in the Internet of Things, Cloud Computing and Social Networking. These advancements have generated a lot of data lately, which has led to a big push for more efficient algorithms and new data structures that should be able to handle all this data. These algorithms and data structures are not only used in instances where there is a lot of data, but also when the resources are limited. This paper mainly focuses on the Count-Min (CM) Sketch, a compact summary data structure that serves as a frequency table of events in a stream of data. We explain the implementation of this data structure and how it can be used in solving problems that appear in different fields of Computer Science, such as solving the frequent items (heavy hitters) problem, speeding up database queries, improving password security and many more. 

Keyphrases: Count-Min Sketch, anomaly detection, computational biology, heavy hitters, streaming algorithms

@booklet{EasyChair:879,
  author    = {Benedikt Sigurleifsson and Aravindan Anbarasu and Karl Kangur},
  title     = {An Overview of Count-Min Sketch and its Applications},
  howpublished = {EasyChair Preprint 879},
  year      = {EasyChair, 2019}}