Java Program to Implement CountMinSketch

This is a Java Program to implement Count Min Sketch. The Count–min sketch (or CM sketch) is a probabilistic sub-linear space streaming algorithm which can be used to summarize a data stream in many different ways. Count–min sketches are somewhat similar to Bloom filters; the main distinction is that Bloom filters represent sets, while CM sketches represent multi-sets and frequency tables.

Here is the source code of the Java program to implement Count Min Sketch. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  * Java Program to Implement CountMinSketch
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. class CountMinSketch
  8. {
  9.     private int[] h1;
  10.     private int[] h2;
  11.     private int[] h3;
  12.     private int size;
  13.     private static int DEFAULT_SIZE = 11;
  14.  
  15.     /** Constructor **/
  16.     public CountMinSketch()
  17.     {
  18.         size = DEFAULT_SIZE;
  19.         h1 = new int[ size ];
  20.         h2 = new int[ size ];
  21.         h3 = new int[ size ];
  22.     }
  23.     /** Function to clear al counters **/
  24.     public void clear()
  25.     {
  26.         size = DEFAULT_SIZE;
  27.         h1 = new int[ size ];
  28.         h2 = new int[ size ];
  29.         h3 = new int[ size ];
  30.     }
  31.     /** Function to insert value **/
  32.     public void insert(int val)
  33.     {
  34.         int hash1 = hashFunc1(val);
  35.         int hash2 = hashFunc2(val);
  36.         int hash3 = hashFunc3(val);
  37.         /** increment counters **/
  38.         h1[ hash1 ]++;
  39.         h2[ hash2 ]++;
  40.         h3[ hash3 ]++;
  41.     }
  42.     /** Function to get sketch count **/
  43.     public int sketchCount(int val)
  44.     {
  45.         int hash1 = hashFunc1(val);
  46.         int hash2 = hashFunc2(val);
  47.         int hash3 = hashFunc3(val);
  48.         return min( h1[ hash1 ], h2[ hash2 ], h3[ hash3 ] );
  49.     }
  50.     private int min(int a, int b, int c)
  51.     {
  52.         int min = a;
  53.         if (b < min)
  54.             min = b;
  55.         if (c < min)
  56.             min = c;
  57.         return min;
  58.     }
  59.     /** Hash function 1 **/
  60.     private int hashFunc1(int val)
  61.     {
  62.         return val % size;
  63.     }
  64.     /** Hash function 2 **/
  65.     private int hashFunc2(int val)
  66.     {
  67.         return ((val * (val + 3)) % size);
  68.     }
  69.     /** Hash function 3 **/
  70.     private int hashFunc3(int val)
  71.     {
  72.         return (size - 1) - val % size;
  73.     }
  74.     /** Funtion to print all tables **/
  75.     public void print()
  76.     {
  77.         System.out.println("\nCounter Tables : \n");
  78.         System.out.print("h1 : ");
  79.         for (int i = 0; i < size; i++)
  80.             System.out.print(h1[i] +" ");
  81.         System.out.print("\nh2 : ");
  82.         for (int i = 0; i < size; i++)
  83.             System.out.print(h2[i] +" ");
  84.         System.out.print("\nh3 : ");
  85.         for (int i = 0; i < size; i++)
  86.             System.out.print(h3[i] +" ");
  87.         System.out.println();
  88.     }    
  89. }
  90.  
  91. public class CountMinSketchTest
  92. {
  93.     public static void main(String[] args)
  94.     {
  95.         Scanner scan = new Scanner(System.in);
  96.         System.out.println("Count Min Sketch Test\n\n");
  97.         /** Make object of CountMinSketch **/
  98.         CountMinSketch cms = new CountMinSketch();
  99.  
  100.         char ch;
  101.         /**  Perform CountMinSketch operations  **/
  102.         do    
  103.         {    
  104.             System.out.println("\nCount Min Sketch Operations\n");
  105.             System.out.println("1. insert ");
  106.             System.out.println("2. get sketch count");
  107.             System.out.println("3. clear");
  108.  
  109.             int choice = scan.nextInt();            
  110.             switch (choice)
  111.             {
  112.             case 1 : 
  113.                 System.out.println("Enter int value");
  114.                 cms.insert(scan.nextInt() ); 
  115.                 break;                          
  116.             case 2 :                 
  117.                 System.out.println("Enter int value");
  118.                 int val = scan.nextInt();
  119.                 System.out.println("\nSketch count for "+ val +" = "+ cms.sketchCount( val )); 
  120.                 break;                        
  121.             case 3 : 
  122.                 cms.clear();
  123.                 System.out.println("Counters Cleared\n");
  124.                 break;
  125.             default : 
  126.                 System.out.println("Wrong Entry \n ");
  127.                 break;   
  128.             }
  129.             /** Display counter table **/
  130.             cms.print();  
  131.  
  132.             System.out.println("\nDo you want to continue (Type y or n) \n");
  133.             ch = scan.next().charAt(0);                        
  134.         } while (ch == 'Y'|| ch == 'y');
  135.     }
  136. }

Count Min Sketch Test
 
 
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
45
 
Counter Tables :
 
h1 : 0 1 0 0 0 0 0 0 0 0 0
h2 : 0 0 0 0 1 0 0 0 0 0 0
h3 : 0 0 0 0 0 0 0 0 0 1 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
67
 
Counter Tables :
 
h1 : 0 2 0 0 0 0 0 0 0 0 0
h2 : 0 0 0 0 2 0 0 0 0 0 0
h3 : 0 0 0 0 0 0 0 0 0 2 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
23
 
Counter Tables :
 
h1 : 0 3 0 0 0 0 0 0 0 0 0
h2 : 0 0 0 0 3 0 0 0 0 0 0
h3 : 0 0 0 0 0 0 0 0 0 3 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
47
 
Counter Tables :
 
h1 : 0 3 0 1 0 0 0 0 0 0 0
h2 : 0 0 0 0 3 0 0 1 0 0 0
h3 : 0 0 0 0 0 0 0 1 0 3 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
23
 
Counter Tables :
 
h1 : 0 4 0 1 0 0 0 0 0 0 0
h2 : 0 0 0 0 4 0 0 1 0 0 0
h3 : 0 0 0 0 0 0 0 1 0 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
31
 
Counter Tables :
 
h1 : 0 4 0 1 0 0 0 0 0 1 0
h2 : 0 0 0 0 4 0 0 1 0 1 0
h3 : 0 1 0 0 0 0 0 1 0 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
59
 
Counter Tables :
 
h1 : 0 4 0 1 1 0 0 0 0 1 0
h2 : 0 0 0 0 4 0 1 1 0 1 0
h3 : 0 1 0 0 0 0 1 1 0 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
13
 
Counter Tables :
 
h1 : 0 4 1 1 1 0 0 0 0 1 0
h2 : 0 0 0 0 4 0 1 1 0 1 1
h3 : 0 1 0 0 0 0 1 1 1 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
17
 
Counter Tables :
 
h1 : 0 4 1 1 1 0 1 0 0 1 0
h2 : 0 0 0 0 4 0 1 1 0 1 2
h3 : 0 1 0 0 1 0 1 1 1 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
2
Enter int value
17
 
Sketch count for 17 = 1
 
Counter Tables :
 
h1 : 0 4 1 1 1 0 1 0 0 1 0
h2 : 0 0 0 0 4 0 1 1 0 1 2
h3 : 0 1 0 0 1 0 1 1 1 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
1
Enter int value
97
 
Counter Tables :
 
h1 : 0 4 1 1 1 0 1 0 0 2 0
h2 : 0 0 0 0 4 0 1 1 0 2 2
h3 : 0 2 0 0 1 0 1 1 1 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
2
Enter int value
97
 
Sketch count for 97 = 2
 
Counter Tables :
 
h1 : 0 4 1 1 1 0 1 0 0 2 0
h2 : 0 0 0 0 4 0 1 1 0 2 2
h3 : 0 2 0 0 1 0 1 1 1 4 0
 
Do you want to continue (Type y or n)
 
y
 
Count Min Sketch Operations
 
1. insert
2. get sketch count
3. clear
3
Counters Cleared
 
 
Counter Tables :
 
h1 : 0 0 0 0 0 0 0 0 0 0 0
h2 : 0 0 0 0 0 0 0 0 0 0 0
h3 : 0 0 0 0 0 0 0 0 0 0 0
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.