Set Similarity with Jaccard Coefficient and MinHash in C++

Introduction

Set similarity measures are essential in various domains, from data mining to natural language processing and information retrieval. They allow us to quantify how similar two sets of data are, enabling applications like clustering, duplicate detection, and recommendation systems.

Among the popular similarity measures, the Jaccard Similarity Coefficient is a widely used mathematical metric for determining the similarity between two sets. However, as datasets grow larger, computing this coefficient can become computationally expensive. This is where the MinHash technique comes into play, offering an efficient way to approximate Jaccard similarity for large-scale data.

In this guide, we will delve into the implementation of both Jaccard Similarity and MinHash in C++. Starting with a theoretical understanding, we will walk through code examples, discuss their computational complexities, and compare their performance. By the end, you’ll have a clear grasp of when to use each method and how to implement them effectively.

Mathematical Background

The Jaccard Similarity Coefficient is a statistical measure used to determine the similarity between two sets. For two sets \( A \) and \( B \), the Jaccard Similarity \( J(A, B) \) is defined mathematically as:

Here:

• \(|A \cap B|\): The number of elements common to both sets \( A \) and \( B \) (intersection).
• \(|A \cup B|\): The total number of unique elements in both sets (union).

The Jaccard Similarity ranges from \( 0 \) (no similarity) to \( 1 \) (identical sets). While it is straightforward for small sets, it becomes computationally expensive for large sets due to two main reasons:

• Calculating the Intersection: Determining \(|A \cap B|\) involves checking every element of one set against the other, which requires \( O(\min(|A|, |B|)) \) operations.
• Calculating the Union: Finding \(|A \cup B|\) requires iterating through both sets to count unique elements, with a time complexity of \( O(|A| + |B|) \).

For large datasets with many sets, the number of pairwise comparisons grows quadratically (\( O(n^2) \)), making Jaccard Similarity computationally infeasible. This is especially problematic in applications like document clustering, recommendation systems, or duplicate detection.

To overcome these challenges, MinHash provides a scalable approximation by reducing each set to a compact signature. This allows similarity calculations to be performed efficiently, even for large-scale datasets.

MinHash Approximation

MinHash is a probabilistic technique that estimates the Jaccard Similarity using hash functions. A hash function is a mathematical function that maps input data to a fixed-size numerical value (a hash), which appears random but is consistent for the same input. Instead of comparing entire sets, MinHash uses the minimum values of hashed elements to approximate similarity. The core idea is:

This means the probability that the minimum hash values of sets \( A \) and \( B \) are equal is equivalent to their Jaccard Similarity. By using multiple hash functions, we can construct a signature matrix for each set, where the similarity of two sets is estimated as the fraction of rows with identical values.

Jaccard Coefficient vs MinHash

While both methods aim to measure set similarity, their characteristics differ:

With this mathematical foundation, we are now ready to explore how to implement these concepts in C++.

Jaccard Similarity Implementation

The Jaccard Similarity Coefficient is computed by dividing the size of the intersection of two sets by the size of their union. This implementation focuses on efficiency, minimizing computational overhead by leveraging unordered sets for constant-time lookups and using a single iteration to compute the intersection and union sizes simultaneously.

// Include necessary libraries
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

// Class definition for Jaccard Similarity
class JaccardSimilarity {
public:
    // Template function for flexibility with different data types
    template<typename T>
    static double calculate(const std::unordered_set<T>& set1,
                            const std::unordered_set<T>& set2) {
        // Early return for empty sets
        if (set1.empty() && set2.empty()) return 1.0;
        if (set1.empty() || set2.empty()) return 0.0;

        size_t intersection = 0, union_size = set1.size() + set2.size();

        // Iterate over the smaller set for better cache performance
        const auto& smaller_set = (set1.size() < set2.size()) ? set1 : set2;
        const auto& larger_set = (set1.size() < set2.size()) ? set2 : set1;

        for (const auto& element : smaller_set) {
            if (larger_set.find(element) != larger_set.end()) {
                intersection++; // Count intersection
            }
        }

        // Calculate union size
        union_size -= intersection;

        // Return the Jaccard similarity
        return static_cast<double>(intersection) / union_size;
    }
};

int main() {
    // Example sets
    std::unordered_set<int> set1 = {1, 2, 3, 4};
    std::unordered_set<int> set2 = {2, 3, 4, 5};

    // Calculate similarity
    double similarity = JaccardSimilarity::calculate(set1, set2);

    // Print the result
    std::cout << "Jaccard similarity: " << similarity << std::endl;

    return 0;
}
        

Example Output

Jaccard similarity: 0.6
        

Key Optimizations

• Early Return: Quickly handles edge cases where one or both sets are empty to avoid unnecessary computations.
• Smaller Set Iteration: Iterates over the smaller set to reduce the number of lookups and improve cache efficiency.
• Union Size Calculation: Avoids redundant computation by subtracting the intersection size from the total size of both sets.
• Unordered Sets: Provides constant-time complexity for insertions and lookups, making the implementation scalable for larger sets.

MinHash Implementation

MinHash provides a probabilistic method to approximate the Jaccard Similarity between two sets. Instead of calculating the exact intersection and union, MinHash computes a signature for each set using multiple hash functions. The similarity is then estimated as the fraction of matching hash values between the signatures of two sets.

This implementation focuses on performance by:

• Precomputing random coefficients for hash functions.
• Using modular arithmetic to efficiently generate hash values.
• Minimizing memory overhead by storing only the smallest hash values for each function.

// Include necessary libraries
#include <iostream>
#include <unordered_set>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

// Class definition for MinHash
class MinHash {
private:
    std::vector<uint32_t> coefficients_a;
    std::vector<uint32_t> coefficients_b;
    const uint32_t prime = 4294967311u; // A prime larger than 2^32
    const size_t num_hashes;

    // Initialize random coefficients for hash functions
    void initialize_coefficients() {
        std::mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
        std::uniform_int_distribution<uint32_t> dist(1, prime - 1);

        for (size_t i = 0; i < num_hashes; ++i) {
            coefficients_a[i] = dist(gen);
            coefficients_b[i] = dist(gen);
        }
    }

public:
    // Constructor to set the number of hash functions
    MinHash(size_t num_hash_functions)
        : num_hashes(num_hash_functions),
          coefficients_a(num_hash_functions),
          coefficients_b(num_hash_functions) {
        initialize_coefficients();
    }

    // Compute MinHash signatures for a set
    std::vector<uint32_t> compute_signature(const std::unordered_set<uint32_t>& input_set) {
        std::vector<uint32_t> signature(num_hashes, UINT32_MAX);

        for (const auto& element : input_set) {
            for (size_t i = 0; i < num_hashes; ++i) {
                // Compute hash: (a * x + b) % p
                uint64_t hash = (static_cast<uint64_t>(coefficients_a[i]) * element
                               + coefficients_b[i]) % prime;
                signature[i] = std::min(signature[i], static_cast<uint32_t>(hash));
            }
        }

        return signature;
    }

    // Estimate Jaccard similarity from MinHash signatures
    static double estimate_similarity(const std::vector<uint32_t>& sig1,
                                      const std::vector<uint32_t>& sig2) {
        if (sig1.size() != sig2.size()) {
            throw std::invalid_argument("Signatures must have equal length");
        }

        size_t matches = 0;
        for (size_t i = 0; i < sig1.size(); ++i) {
            if (sig1[i] == sig2[i]) {
                matches++;
            }
        }

        return static_cast<double>(matches) / sig1.size();
    }
};

int main() {
    // Example sets
    std::unordered_set<uint32_t> set1 = {1, 2, 3, 4};
    std::unordered_set<uint32_t> set2 = {2, 3, 4, 5};

    // Initialize MinHash with 100 hash functions
    MinHash minhash(100);

    // Compute signatures
    auto sig1 = minhash.compute_signature(set1);
    auto sig2 = minhash.compute_signature(set2);

    // Estimate similarity
    double estimated_similarity = MinHash::estimate_similarity(sig1, sig2);

    // Print the result
    std::cout << "Estimated Jaccard similarity: " << estimated_similarity << std::endl;

    return 0;
}
        

Example Output

Estimated Jaccard similarity: 0.6
        

Key Optimizations

• Precomputed Hash Coefficients: Avoids recalculating random coefficients during signature computation, saving time for large datasets.
• Minimizing Memory Use: Stores only the minimum hash values instead of all hashed elements, reducing memory overhead.
• Parallelizable: The MinHash computation for each hash function is independent, making it suitable for parallel processing.

Performance Comparison

To understand the performance differences between Jaccard Similarity and MinHash, we ran benchmarks using multiple sets of varying sizes. The goal was to measure the time taken for both methods to compute pairwise similarities across these sets.

While Jaccard Similarity computes exact results, it becomes computationally expensive for large datasets due to its reliance on set operations. In contrast, MinHash provides an approximate similarity measure and scales better for larger datasets by leveraging precomputed signatures.

Complexity Analysis

The complexities of Jaccard Similarity and MinHash are summarized below:

Benchmark Implementation

The performance test generates random sets, calculates pairwise similarities using both Jaccard Similarity and MinHash, and measures the execution time for each. The implementation is divided into three files: the MinHash header, the JaccardSimilarity header, and the main benchmarking code.

Benchmarking Code

The following C++ code benchmarks Jaccard Similarity and MinHash for multiple sets. It generates random sets, computes their MinHash signatures, and compares the performance of estimating similarities using MinHash versus directly calculating Jaccard Similarity for each pair:

#ifndef JACCARD_SIMILARITY_H
#define JACCARD_SIMILARITY_H

#include <unordered_set>

class JaccardSimilarity {
public:
    template<typename T>
    static double calculate(const std::unordered_set<T>& set1, const std::unordered_set<T>& set2) {
        if (set1.empty() && set2.empty()) return 1.0;
        if (set1.empty() || set2.empty()) return 0.0;

        size_t intersection = 0, union_size = set1.size() + set2.size();
        const auto& smaller = (set1.size() < set2.size()) ? set1 : set2;
        const auto& larger = (set1.size() < set2.size()) ? set2 : set1;

        for (const auto& element : smaller) {
            if (larger.find(element) != larger.end()) {
                intersection++;
            }
        }
        union_size -= intersection;
        return static_cast<double>(intersection) / union_size;
    }
};

#endif // JACCARD_SIMILARITY_H
    

#ifndef MINHASH_H
#define MINHASH_H

#include <vector>
#include <unordered_set>
#include <random>
#include <chrono>
#include <algorithm>

class MinHash {
private:
    std::vector<uint32_t> coefficients_a;
    std::vector<uint32_t> coefficients_b;
    const uint32_t prime = 4294967311u;
    const size_t num_hashes;

    void initialize_coefficients() {
        std::mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
        std::uniform_int_distribution<uint32_t> dist(1, prime - 1);
        for (size_t i = 0; i < num_hashes; ++i) {
            coefficients_a[i] = dist(gen);
            coefficients_b[i] = dist(gen);
        }
    }

public:
    MinHash(size_t num_hash_functions)
        : num_hashes(num_hash_functions),
          coefficients_a(num_hash_functions),
          coefficients_b(num_hash_functions) {
        initialize_coefficients();
    }

    std::vector<uint32_t> compute_signature(const std::unordered_set<uint32_t>& input_set) {
        std::vector<uint32_t> signature(num_hashes, UINT32_MAX);
        for (const auto& element : input_set) {
            for (size_t i = 0; i < num_hashes; ++i) {
                uint64_t hash = (static_cast<uint64_t>(coefficients_a[i]) * element + coefficients_b[i]) % prime;
                signature[i] = std::min(signature[i], static_cast<uint32_t>(hash));
            }
        }
        return signature;
    }

    static double estimate_similarity(const std::vector<uint32_t>& sig1, const std::vector<uint32_t>& sig2) {
        size_t matches = 0;
        for (size_t i = 0; i < sig1.size(); ++i) {
            if (sig1[i] == sig2[i]) matches++;
        }
        return static_cast<double>(matches) / sig1.size();
    }
};

#endif // MINHASH_H
    

#include <iostream>
#include <vector>
#include <unordered_set>
#include <random>
#include <chrono>
#include <iomanip>
#include "JaccardSimilarity.h"
#include "MinHash.h"

class Timer {
public:
    void start() {
        start_time = std::chrono::high_resolution_clock::now();
    }
    void stop() {
        end_time = std::chrono::high_resolution_clock::now();
    }
    double elapsed_ms() {
        return std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();
    }
private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_time, end_time;
};

std::unordered_set<uint32_t> generate_random_set(size_t size, std::mt19937& gen,
                                                std::uniform_int_distribution<uint32_t>& dist) {
    std::unordered_set<uint32_t> set;
    while (set.size() < size) {
        set.insert(dist(gen));
    }
    return set;
}

void run_performance_test(const std::vector<size_t>& set_sizes,
                         const std::vector<size_t>& num_sets_list,
                         size_t num_hash_functions) {
    std::mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<uint32_t> dist(1, 1000000);
    Timer timer;

    // Print header
    std::cout << "\nPerformance Test Results\n";
    std::cout << "=======================\n";
    std::cout << std::setw(15) << "Set Size"
              << std::setw(15) << "Num Sets"
              << std::setw(20) << "Jaccard Time (ms)"
              << std::setw(20) << "MinHash Time (ms)" << std::endl;
    std::cout << std::string(70, '-') << std::endl;

    for (size_t set_size : set_sizes) {
        for (size_t num_sets : num_sets_list) {
            // Generate random sets
            std::vector<std::unordered_set<uint32_t>> sets;
            for (size_t i = 0; i < num_sets; ++i) {
                sets.push_back(generate_random_set(set_size, gen, dist));
            }

            // Test Jaccard Similarity
            timer.start();
            for (size_t i = 0; i < num_sets; ++i) {
                for (size_t j = i + 1; j < num_sets; ++j) {
                    JaccardSimilarity::calculate(sets[i], sets[j]);
                }
            }
            timer.stop();
            double jaccard_time = timer.elapsed_ms();

            // Test MinHash
            MinHash minhash(num_hash_functions);

            timer.start();
            // Compute signatures
            std::vector<std::vector<uint32_t>> signatures;
            for (const auto& set : sets) {
                signatures.push_back(minhash.compute_signature(set));
            }

            // Compare signatures
            for (size_t i = 0; i < num_sets; ++i) {
                for (size_t j = i + 1; j < num_sets; ++j) {
                    MinHash::estimate_similarity(signatures[i], signatures[j]);
                }
            }
            timer.stop();
            double minhash_time = timer.elapsed_ms();

            // Print results
            std::cout << std::setw(15) << set_size
                      << std::setw(15) << num_sets
                      << std::setw(20) << std::fixed << std::setprecision(2) << jaccard_time
                      << std::setw(20) << minhash_time << std::endl;
        }
    }
}

int main() {
    // Test parameters
    std::vector<size_t> set_sizes = {1000, 5000, 10000};
    std::vector<size_t> num_sets_list = {10, 100, 1000};
    size_t num_hash_functions = 100;

    std::cout << "Starting performance tests...\n";
    std::cout << "Number of hash functions for MinHash: " << num_hash_functions << "\n";

    run_performance_test(set_sizes, num_sets_list, num_hash_functions);

    return 0;
}
    

Performance Test Results

Use Cases

Jaccard Similarity and MinHash have diverse applications across multiple domains, thanks to their ability to efficiently compare sets and approximate similarity. Below are some key use cases categorized for better understanding.

1. Document Similarity

Both Jaccard Similarity and MinHash are widely used in document similarity tasks. By representing documents as sets of words (or shingles, which are contiguous subsequences of words), their similarity can be computed to identify near-duplicate documents or clustered into similar groups.

• Plagiarism Detection: Comparing essays, research papers, or web articles for overlapping content.
• Search Engines: Identifying similar pages to consolidate search results or detect duplicate content.

2. Duplicate Detection

In large datasets, finding near-duplicate items is essential for cleaning and maintaining data quality. Jaccard Similarity works well for smaller datasets, while MinHash scales effectively for large, distributed systems.

• E-commerce: Detecting duplicate product listings based on descriptions or tags.
• Databases: Removing duplicate records in structured or semi-structured data.

3. Recommendation Systems

Recommendation systems leverage set similarity to match users or items. For example, in collaborative filtering, users are grouped based on shared preferences or activities, and recommendations are made by comparing these sets.

• Streaming Platforms: Suggesting movies or songs based on viewing or listening history.
• E-commerce: Recommending products based on shared purchasing patterns.

4. Clustering and Classification

Set similarity is critical in clustering algorithms, where data points are grouped into similar clusters. MinHash is particularly effective in large-scale clustering tasks where exact similarity measures would be computationally expensive.

• Natural Language Processing: Grouping similar text documents or tweets into topics.
• Image Processing: Clustering similar images based on shared features or tags.

5. Bioinformatics

In bioinformatics, Jaccard Similarity and MinHash help analyze DNA or protein sequences by representing sequences as sets of k-mers (subsequences of length \( k \)).

• Genome Analysis: Identifying similar genomes by comparing k-mers.
• Protein Sequence Matching: Finding similar protein structures or functions.

6. Network Analysis

Graph-based representations often involve comparing neighborhoods of nodes (sets of connected nodes). MinHash is used to quickly approximate similarity in such scenarios, especially in large-scale social or transportation networks.

• Social Networks: Detecting communities by comparing user connections.
• Transportation Networks: Identifying overlapping routes or hubs in logistics systems.

7. Streaming and Real-Time Applications

MinHash’s ability to process data incrementally makes it ideal for streaming data applications. By maintaining compact signatures, it can approximate similarity in real-time.

• Fraud Detection: Monitoring streaming transactions for near-duplicate activities.
• Log Analysis: Identifying similar patterns in log entries for anomaly detection.

Conclusion

In this guide, we explored two powerful methods for measuring set similarity: Jaccard Similarity and MinHash. Each has unique strengths and is suited for specific use cases:

• Jaccard Similarity: Ideal for smaller datasets or scenarios where exact similarity calculations are required. It’s simple to implement but computationally expensive for large-scale comparisons.
• MinHash: A scalable approximation technique for large datasets or high-frequency comparisons. By leveraging compact signatures, it balances efficiency and accuracy effectively.

The benchmarking results demonstrated MinHash’s advantage in scalability while highlighting Jaccard’s precision. Selecting the right method depends on your dataset size, performance needs, and tolerance for approximation.

Set similarity plays a crucial role in fields like recommendation systems, document clustering, and duplicate detection. By understanding these methods, you can confidently integrate efficient similarity computations into your applications.

Thank you for reading! If you found this guide helpful, please share it using the Attribution and Citation buttons below. For more insights, check out the Further Reading section.

Happy coding!