Count Min sketch is a simple technique to summarize large amounts of frequency data. which is widely used in many places where there is a streaming big data.

Donate/Patreon: https://www.patreon.com/techdummies

CODE:
----------------------------------------------------------------------------
By Varun Vats: https://gist.github.com/VarunVats9/7f379199d7658b96d479ee3c945f1b4a


Applications of count min sketch:
----------------------------------------------------------------------------
http://theory.stanford.edu/~tim/s15/l/l2.pdf
http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html
https://spark.apache.org/docs/2.0.1/api/java/org/apache/spark/util/sketch/CountMinSketch.html

Applications using Count Tracking There are dozens of applications of count tracking and in particular, the Count-Min sketch datastructure that goes beyond the task of approximating data distributions. We give three examples.
1. A more general query is to identify the Heavy-Hitters, that is, the query HH(k) returns theset of items which have large frequency (say 1/k of the overall frequency). Count trackingcan be used to directly answer this query, by considering the frequency of each item. Whenthere are very many possible items, answering the query in this way can be quite slow. Theprocess can be sped up immensely by keeping additional information about the frequenciesof groups of items [6], at the expense of storing additional sketches. As well as being ofinterest in mining applications, finding heavy-hitters is also of interest in the context of signalprocessing. Here, viewing the signal as defining a data distribution, recovering the heavy-hitters is key to building the best approximation of the signal. As a result, the Count-Minsketch can be used in compressed sensing, a signal acquisition paradigm that has recentlyrevolutionized signal processing [7].
2. One application where very large data sets arise is in Natural Language Processing (NLP).Here, it is important to keep statistics on the frequency of word combinations, such as pairsor triplets of words that occur in sequence. In one experiment, researchers compacted a large6
Page 7
90GB corpus down to a (memory friendly) 8GB Count-Min sketch [8]. This proved to be justas effective for their word similarity tasks as using the exact data.
3. A third example is in designing a mechanism to help users pick a safe password. To makepassword guessing difficult, we can track the frequency of passwords online and disallowcurrently popular ones. This is precisely the count tracking problem. Recently, this wasput into practice using the Count-Min data structure to do count tracking (see http://www.youtube.com/watch?v=qo1cOJFEF0U). A nice feature of this solution is that the impactof a false positive—erroneously declaring a rare password choice to be too popular and sodisallowing it—is only a mild inconvenience to the user

Tech Dummies - Narendra L

Count-Min Sketch is a probabilistic data structure that uses multiple hash functions and a fixed-size 2D matrix to count event frequencies in streaming data with sub-linear space. Unlike hash tables, its memory footprint stays constant regardless of input size, making it ideal for infinite or high-volume data streams. The trade-off is occasional over-counting due to hash collisions, never under-counting. The tutorial walks through how the sketch is populated by hashing each element and incrementing matrix cells, and how frequency queries are answered by taking the minimum value across all hash function rows. Applications include NLP, compressed sensing, networking, and streaming platforms like Apache Storm and Flink.

Count min sketch | Efficient algorithm for counting stream of data | system design components