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.

/**
 * 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:

Login For a Spring Web App – Error Handling and Localization
Spring Boot - Google OAuth2 Sign-In
RestTemplate Post Request with JSON
Java Program to Implement LinkedTransferQueue API
Setting the Java Version in Maven
Generating Random Numbers in a Range in Java
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Using Spring @ResponseStatus to Set HTTP Status Code
A Guide to System.exit()
Java Program to Implement the RSA Algorithm
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Spring Cloud – Tracing Services with Zipkin
Java Program to Compute the Area of a Triangle Using Determinants
Difference Between Wait and Sleep in Java
Spring Data JPA Delete and Relationships
Guide to System.gc()
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java
Java Program to Generate a Random UnDirected Graph for a Given Number of Edges
Convert Character Array to String in Java
Versioning a REST API
Java Program to Perform Uniform Binary Search
How to Store Duplicate Keys in a Map in Java?
Spring Boot Actuator
Prevent Brute Force Authentication Attempts with Spring Security
An Introduction to ThreadLocal in Java
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Check If Two Lists are Equal in Java
Java toString() Method
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Perform Insertion in a 2 Dimension K-D Tree
HttpClient Timeout
Base64 encoding và decoding trong Java 8