Concept of the day1 / 3
Locality-sensitive hashing
The conceptHow a search engine spots two near-identical pages among billions
Locality-sensitive hashing (LSH) is a hash built so that similar items get similar fingerprints. An ordinary hash scatters inputs: change one comma and its output changes completely. LSH makes close inputs collide on purpose.
SimHash is one version. Turn a page into a vector, a list of word counts. For each of 64 random directions, record 1 if the page lies on that direction's side, else 0. The 64 bits form its fingerprint.
What it’s forGives the chance that two items get the same bit from one random direction.
P(same bit) = 1 − θ / 180°
- θ
- the angle between the two items' vectors: 0° for identical pages, 90° for unrelated ones
- P
- the probability that one random dividing plane puts both items on the same side
What it givesThe more alike two pages are, the closer to 1 the chance that their bits match.
- Two pages whose vectors are 36° apart: 1 − 36/180 = 1 − 0.2 = 0.8
- Across 64 bits, expect about 64 × 0.8 ≈ 51 matching bits
- Unrelated pages at 90°: 1 − 90/180 = 0.5, so about 32 bits match, as if by chance