Loading...
Please wait, while we are loading the content...
Similar Documents
EasyChair Preprint No 879 An Overview of Count-Min Sketch and its Applications
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sigurleifsson, Benedikt Anbarasu, Aravindan Kangur, Karl |
| 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 (IoT), Cloud Computing and Social Networking [9]. These new technologies and devices generate a lot of data, which causes problems related to storing and processing it. This has led to a push for more efficient algorithms and new data structures that should work on top-of-theline hardware as well as on small IoT devices with limited resources. All with the aim of handling more data than ever before. This paper mainly focuses on the Count-Min (CM) Sketch [6], which is a compact summary data structure that serves as a frequency table of events in a stream of data. The paper explains the implementation of this data structure and shows that 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. We also briefly introduce the Bloom filter [2] which is a related data structure that the CM builds upon. This paper signifies the importance of Count-Min sketch in Computer Science by describing the wide array of applications it is used in. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://easychair.org/publications/preprint_open/gNlw |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
