How does Count-Min Sketch work?

Let’s look at the below example step by step. 

Creating a Count-Min Sketch using Matrix

• Consider the below 2D array with 4 rows and 16 columns, also the number of rows is equal to the number of hash functions. That means we are taking four hash functions for our example. Initialize/mark each cell in the matrix with zero. 

Note: The more accurate result you want, the more hash function to be used. 

Now let’s add some elements (Input) to the Count-Min Sketch.

To do so we have to pass that element with all four hash functions which will result as follows. 

• Input 1: 192.170.0.1

Passing the input through Hash Functions:

• hashFunction1(192.170.0.1): 1
• hashFunction2(192.170.0.1): 6
• hashFunction3(192.170.0.1): 3
• hashFunction4(192.170.0.1): 1

Now visit the indexes retrieved above by all four hash functions and mark them as 1. 

• Input 2: 75.245.10.1  

Passing the input through Hash Functions:

• hashFunction1(75.245.10.1): 1
• hashFunction2(75.245.10.1): 2
• hashFunction3(75.245.10.1): 4
• hashFunction4(75.245.10.1): 6

Now visit the indexes retrieved above by all four hash functions and mark them as 1. 

Now, take these indexes and visit the matrix, if the given index has already been marked as 1. This is called collision, i.e., the index of that row was already marked by some previous inputs.

In this case, just increment the index value by 1.

In our case, since we have already marked index 1 of row 1 i.e., hashFunction1() as 1 by previous input, so this time it will be incremented by 1, and now this cell entry will be 2, but for the rest of the index of rest rows, it will be 0, since there was no collision. 

• Input 3: 10.125.22.20  

Passing the input through Hash Functions:

• hashFunction1(10.125.22.20): 3
• hashFunction2(10.125.22.20): 4
• hashFunction3(10.125.22.20): 1
• hashFunction4(10.125.22.20): 6

Lets, represent it on matrix, do remember to increment the count by 1 if already some entry exist. 

 

• Input 4: 192.170.0.1  

Passing the input through Hash Functions:

• hashFunction1(192.170.0.1): 1
• hashFunction2(192.170.0.1): 6
• hashFunction3(192.170.0.1): 3
• hashFunction4(192.170.0.1): 1

Lets, represent it on matrix, do remember to increment the count by 1 if already some entry exist. 

Testing Count-Min Sketch data structure against Test cases:

Now let’s test some element and check how many time are they present. 

• Input 1: 192.170.0.1

Pass above input to all four hash functions, and take the index numbers generated by hash functions. 

• hashFunction1(192.170.0.1): 1
• hashFunction2(192.170.0.1): 6
• hashFunction3(192.170.0.1): 3
• hashFunction4(192.170.0.1): 1

Now visit to each index and take note down the entry present on that index. 

So the final entry on each index was 3, 2, 2, 2.

Now take the minimum count among these entries and that is the result. So min(3, 2, 2, 2) is 2, that means the above test input is processed 2 times in the above list. 

Hence Output (Frequency of 192.170.0.1) = 2.

• Input 2: 10.125.22.20

Pass above input to all four hash functions, and take the index numbers generated by hash functions. 

• hashFunction1(10.125.22.20): 3
• hashFunction2(10.125.22.20): 4
• hashFunction3(10.125.22.20): 1
• hashFunction4(10.125.22.20): 6

Now visit to each index and take note down the entry present on that index. 

So the final entry on each index was 1, 1, 1, 2.

Now take the minimum count among these entries and that is the result. So min(1, 1, 1, 2) is 1, that means the above test input is processed only once in the above list.

Hence Output (Frequency of 10.125.22.20) = 1.

The Count-Min Sketch is a probabilistic data structure and is defined as a simple technique to summarize large amounts of frequency data. Count-min sketch algorithm talks about keeping track of the count of things. i.e, How many times an element is present in the set.