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.
/** * Java Program to Implement CountMinSketch **/ import java.util.Scanner; class CountMinSketch { private int[] h1; private int[] h2; private int[] h3; private int size; private static int DEFAULT_SIZE = 11; /** Constructor **/ public CountMinSketch() { size = DEFAULT_SIZE; h1 = new int[ size ]; h2 = new int[ size ]; h3 = new int[ size ]; } /** Function to clear al counters **/ public void clear() { size = DEFAULT_SIZE; h1 = new int[ size ]; h2 = new int[ size ]; h3 = new int[ size ]; } /** Function to insert value **/ public void insert(int val) { int hash1 = hashFunc1(val); int hash2 = hashFunc2(val); int hash3 = hashFunc3(val); /** increment counters **/ h1[ hash1 ]++; h2[ hash2 ]++; h3[ hash3 ]++; } /** Function to get sketch count **/ public int sketchCount(int val) { int hash1 = hashFunc1(val); int hash2 = hashFunc2(val); int hash3 = hashFunc3(val); return min( h1[ hash1 ], h2[ hash2 ], h3[ hash3 ] ); } private int min(int a, int b, int c) { int min = a; if (b < min) min = b; if (c < min) min = c; return min; } /** Hash function 1 **/ private int hashFunc1(int val) { return val % size; } /** Hash function 2 **/ private int hashFunc2(int val) { return ((val * (val + 3)) % size); } /** Hash function 3 **/ private int hashFunc3(int val) { return (size - 1) - val % size; } /** Funtion to print all tables **/ public void print() { System.out.println("\nCounter Tables : \n"); System.out.print("h1 : "); for (int i = 0; i < size; i++) System.out.print(h1[i] +" "); System.out.print("\nh2 : "); for (int i = 0; i < size; i++) System.out.print(h2[i] +" "); System.out.print("\nh3 : "); for (int i = 0; i < size; i++) System.out.print(h3[i] +" "); System.out.println(); } } public class CountMinSketchTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Count Min Sketch Test\n\n"); /** Make object of CountMinSketch **/ CountMinSketch cms = new CountMinSketch(); char ch; /** Perform CountMinSketch operations **/ do { System.out.println("\nCount Min Sketch Operations\n"); System.out.println("1. insert "); System.out.println("2. get sketch count"); System.out.println("3. clear"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter int value"); cms.insert(scan.nextInt() ); break; case 2 : System.out.println("Enter int value"); int val = scan.nextInt(); System.out.println("\nSketch count for "+ val +" = "+ cms.sketchCount( val )); break; case 3 : cms.clear(); System.out.println("Counters Cleared\n"); break; default : System.out.println("Wrong Entry \n "); break; } /** Display counter table **/ cms.print(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
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
Related posts:
Java TreeMap vs HashMap
Java Program to Find Nearest Neighbor for Dynamic Data Set
Immutable Map Implementations in Java
So sánh HashSet, LinkedHashSet và TreeSet trong Java
How to Get the Last Element of a Stream in Java?
Spring Data – CrudRepository save() Method
Extra Login Fields with Spring Security
Convert Time to Milliseconds in Java
Java Program to Represent Graph Using Incidence Matrix
Template Engines for Spring
Java Program to Construct a Random Graph by the Method of Random Edge Selection
Giới thiệu về Stream API trong Java 8
Java Program to Implement Self Balancing Binary Search Tree
Java Program to Check Whether Graph is DAG
Apache Commons Collections SetUtils
New Features in Java 12
Java Program to Solve a Matching Problem for a Given Specific Case
Comparing Two HashMaps in Java
Java Program to Implement Karatsuba Multiplication Algorithm
Java Program to Implement Rope
How to Use if/else Logic in Java 8 Streams
Spring Security OAuth2 – Simple Token Revocation
Java 8 Stream findFirst() vs. findAny()
Read an Outlook MSG file
Java InputStream to String
Java Program to Decode a Message Encoded Using Playfair Cipher
Giới thiệu SOAP UI và thực hiện test Web Service
Java Program to Implement IdentityHashMap API
Java Program to implement Dynamic Array
Java program to Implement Tree Set
@Order in Spring
Guide to Escaping Characters in Java RegExps