How SimHash Generates Locality-Sensitive Hashes

SimHash is a locality-sensitive hashing (LSH) algorithm designed to detect near-duplicate items by mapping high-dimensional data into compact binary fingerprints. Unlike cryptographic hash functions where a tiny change in input causes an avalanche of bit changes, SimHash ensures that documents with high semantic similarity produce hashes with very low Hamming distances. This article explains the step-by-step mathematical process of how SimHash constructs these binary fingerprints and preserves semantic closeness in the binary number system.

1. Feature Extraction and Weighting

The process begins by tokenizing the input document into distinct features, such as words, n-grams, or shingles. Each feature is assigned a weight based on its importance, commonly determined by term frequency, TF-IDF, or custom domain weights. Highly significant words receive larger weights, ensuring they have a stronger influence on the final hash.

2. Individual Feature Hashing

Each extracted feature is hashed independently using a standard, uniform hashing function (such as MD5 or MurmurHash) to produce a fixed-length binary string of \(b\) bits (typically 64 or 128 bits). At this stage, the individual feature hashes are uniformly distributed and non-locality-sensitive.

3. Vector Accumulation

To combine all feature hashes into a single representation, an accumulator vector \(V\) of length \(b\) is initialized with all zeros. For each feature: - The algorithm inspects every bit position \(i\) (from 1 to \(b\)) of the feature’s standard hash. - If the \(i\)-th bit is 1, the feature’s weight \(w\) is added to \(V[i]\). - If the \(i\)-th bit is 0, the feature’s weight \(w\) is subtracted from \(V[i]\).

This weighted summation aggregates the directional contributions of every token across all \(b\) dimensions.

4. Quantization to a Binary Fingerprint

Once all features are processed, the real-valued vector \(V\) is converted back into a \(b\)-bit binary fingerprint: - If \(V[i] > 0\), the \(i\)-th bit of the final SimHash is set to 1. - If \(V[i] \le 0\), the \(i\)-th bit of the final SimHash is set to 0.

Capturing Semantic Differences via Hamming Distance

The geometry behind SimHash relies on the projection of feature vectors across random hyperplanes. When two documents share the majority of their text, their accumulator vectors accumulate weights in the same direction at most bit positions. Consequently, the signs of \(V[i]\) across both documents remain identical for the vast majority of the \(b\) dimensions.

When converted to binary, this sign alignment means the two documents share nearly identical bit sequences. The difference between two documents is measured by their Hamming distance—the count of differing bit positions (computed via an XOR operation followed by a population count). Minor edits, word substitutions, or small deletions only shift the sums slightly, causing few, if any, bit flips. As a result, small semantic differences directly correspond to small Hamming distances, enabling rapid, large-scale similarity lookups.