Understanding MinHash and Jaccard Similarity in Bitsets

This article explores Min-wise hashing (MinHash), an algorithmic technique designed to rapidly estimate the Jaccard similarity between high-dimensional binary datasets. You will learn how documents represented as binary characteristic vectors (bitsets) are transformed into compact signatures, why the probability of hash collision equals the exact Jaccard similarity, and how this method eliminates the computational bottleneck of comparing massive sets.

The Foundation: Jaccard Similarity on Binary Bitsets

In information retrieval and data mining, documents are commonly converted into sets of features (such as character n-grams or word shingles). When defined over a fixed vocabulary of size \(V\), any document can be represented in the binary number system as a characteristic bitset:

\[\mathbf{d} = [b_1, b_2, \dots, b_V] \quad \text{where } b_i \in \{0, 1\}\]

A bit value of 1 signifies the presence of a specific feature, while 0 denotes its absence.

The Jaccard similarity coefficient \(J(A, B)\) measures the overlap between two binary document vectors \(A\) and \(B\):

\[J(A, B) = \frac{|A \cap B|}{|A \cup B|}\]

In binary vector arithmetic, this translates directly to bitwise operations:

\[J(A, B) = \frac{\text{popcount}(A \text{ AND } B)}{\text{popcount}(A \text{ OR } B)}\]

While computing bitwise operations is fast for small datasets, calculating exact Jaccard similarity across millions of high-dimensional vectors requires \(O(V)\) operations per pair, leading to an intractable \(O(N^2 V)\) complexity for pairwise document deduplication.

What is Min-wise Hashing (MinHash)?

Min-wise hashing is a dimensionality reduction technique belonging to the family of Locality-Sensitive Hashing (LSH). Invented by Andrei Broder, MinHash compresses sparse binary bitsets of arbitrary length \(V\) into dense, fixed-length signature vectors of size \(k\) (where \(k \ll V\)) while preserving pairwise Jaccard similarity.

Instead of comparing millions of bits directly, systems compare small signature arrays using simple element-wise equality.

The Mathematical Mechanism: Why MinHash Works

Consider a characteristic matrix where rows correspond to unique vocabulary features and columns correspond to document bitsets.

If you randomly permute the rows of this matrix, the MinHash function \(h_\pi(D)\) returns the index of the first row (under permutation \(\pi\)) where document \(D\) contains a 1.

When comparing two document bitsets \(A\) and \(B\), any given row in the matrix falls into one of three categories:

  1. Type X (1, 1): Both documents have a 1 (Intersection).
  2. Type Y (1, 0) or (0, 1): One document has a 1 and the other has a 0 (Symmetric Difference).
  3. Type Z (0, 0): Both documents have a 0 (Neither contains the feature).

When scanning from the top of the permuted matrix downward: * Type Z rows are ignored because neither document has an active bit. * The first row encountered with a 1 in either document must be either Type X or Type Y. * The probability that the first non-zero bit belongs to Type X (meaning \(h_\pi(A) = h_\pi(B)\)) is the count of Type X rows divided by the total count of Type X and Type Y rows.

Because Type X represents \(|A \cap B|\) and Type X + Type Y represents \(|A \cup B|\):

\[\Pr[h_\pi(A) = h_\pi(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A, B)\]

This equality is the core foundation of MinHash: the probability that two permuted bitsets produce the exact same minimum row index is precisely their Jaccard similarity.

Practical Implementation with Hash Functions

Permuting an entire vocabulary matrix of size \(V\) is computationally prohibitive. In practice, permutations are simulated using \(k\) independent hash functions:

\[h_i(r) = (a_i \cdot r + b_i) \pmod p\]

Where \(r\) is the row index (the bit position where a bit is 1), \(a_i\) and \(b_i\) are random integers, and \(p\) is a prime number greater than \(V\).

The MinHash Algorithm:

  1. Initialize a MinHash signature vector \(S_D\) of size \(k\) for document \(D\) with all values set to \(\infty\).
  2. For each active bit index \(r\) where \(D[r] == 1\):
    • For each hash function \(h_i\) (from \(i = 1\) to \(k\)):
      • Compute \(hash\_val = h_i(r)\).
      • If \(hash\_val < S_D[i]\), update \(S_D[i] = hash\_val\).
  3. The resulting array \(S_D = [s_1, s_2, \dots, s_k]\) serves as the compact signature for document \(D\).

Estimating Jaccard Similarity

Once signature vectors are generated, the Jaccard similarity between document \(A\) and document \(B\) is estimated by counting the proportion of identical components in their signature arrays:

\[J_{est}(A, B) = \frac{1}{k} \sum_{i=1}^{k} \mathbb{I}(S_A[i] == S_B[i])\]

Where \(\mathbb{I}\) is the indicator function returning 1 if the condition is true and 0 otherwise.

The expected error of this estimation decreases as the signature size \(k\) increases, governed by standard variance:

\[\text{Standard Error} \approx \frac{1}{\sqrt{k}}\]

Using \(k = 100\) produces an estimate with an expected error margin of roughly \(10\%\), while \(k = 400\) reduces the margin to \(5\%\), allowing high-precision comparisons in constant \(O(k)\) time regardless of the original bitset dimension.