SimHash
SimHash is the locality-sensitive hash (LSH) proposed by Charikar: it maps text to a fixed-length bit string where similar texts have small Hamming distances.
Purpose
It finds near-duplicate documents with O(1) comparisons across large text collections, supporting deduplication and clustering.
Mechanism
Each feature of the text (e.g., an N-gram) is hashed independently; feature weights are added or subtracted per hash bit according to its 0/1 value, and the final sign bits form the SimHash fingerprint. Higher similarity means a smaller Hamming distance.
Use cases
- Large-scale web page deduplication
- Near-duplicate document clustering
- Plagiarism detection