1 Locality Sensitive Hash Functions

In this lecture we will be talking about algorithms for estimating similarity. Fix a collection C of objects. We define a similarity function sim(x, y) that maps pairs of objects x, y ∈ C to a number in [0, 1]. sim(x, y) measures the similarity between x and y. sim(x, y) = 1 means that x and y are identical; sim(x, y) = 0 means that x and y are very different. For example when C is a set of unit vectors in R d, we can define sim(�u, �v) to be 1 − θ(�u, �v)/π where θ(�u, �v) is the angle between �u and �v. Given C and sim(x, y), a locality sensitive hash function family F operates on C, such that for any x, y ∈ C, Probh∈F[h(x) = h(y)] = sim(x, y) Below are two examples of locality sensitive hash function family. • C is a collection of sets. For two sets A, B ∈ C, sim(A, B) = |A ∩ B|/|A ∪ B|. Broder et al. [1] introduced the notion of min-wise independent permutations, which can be used to construct locality sensitive hash functions for this similarity measure, known as the Jaccard coefficient. • C is a collection of unit vectors. For two vectors �u, �v, sim(�u, �v) = 1 − θ(�u, �v)/π wher