Locality-sensitive hashing

Locality Sensitive Hashing (LSH) is a method of performing probabalistic dimension reduction of high-dimensional data. The basic idea is to Hash Function the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items).

Definition

A locality sensitive hashing scheme is defined with respect to a universe of items $U$ and a distance Metric (mathematics) $\phi :U\times U\to [0,1]$. An LSH scheme is a family of hash functions $H$ coupled with a distribution $D$ over the functions such that a function $h\in H$ chosen randomly according to $D$ satifies the property that $Pr[h(a)=h(b)]=\phi (a,b)$ for any $a,b\in U$.

Applications

LSH has been applied to several problem domains including

• Near Duplicate Algorithms
• Image Similarity Identification
• Gene Expression Similarity Identification
• Audio Similarity Identification

Related Papers

• Charikar, M.S. Estimation Techniques From Rounding Algorithms.
• Broder, A., Charikar, M.S., Frieze, A., Mitzenmacher, M., Independent Permutations