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:
Introduction to Spring Method Security
Java Program to Describe the Representation of Graph using Adjacency List
Java Program to Implement Heap
Guide to @JsonFormat in Jackson
Java Program to Find Number of Articulation points in a Graph
“Stream has already been operated upon or closed” Exception in Java
Hướng dẫn Java Design Pattern – Strategy
Automatic Property Expansion with Spring Boot
Java Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time
Generating Random Dates in Java
Java Program to Implement Sieve Of Sundaram
Lấy ngày giờ hiện tại trong Java
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Java Program to Find a Good Feedback Edge Set in a Graph
Spring Data JPA @Modifying Annotation
Lập trình mạng với java
Giới thiệu luồng vào ra (I/O) trong Java
Properties with Spring and Spring Boot
Java Program to Implement Expression Tree
Guide to Apache Commons CircularFifoQueue
Java Program to Implement Adjacency List
Debug a HttpURLConnection problem
Giới thiệu Json Web Token (JWT)
Spring Boot - Twilio
Spring Boot with Multiple SQL Import Files
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Spring Cloud AWS – EC2
Java Program to Implement ConcurrentLinkedQueue API
Introduction to the Java ArrayDeque
Spring 5 Testing with @EnabledIf Annotation
Guide to CopyOnWriteArrayList
Lập trình đa luồng với CompletableFuture trong Java 8