Passion is like genius; a miracle.

Jaccard index에 대한 언급은 여기에서 앞서서 했음. Jaccard Index는 두개 셋간의 유사성을 계산하므로.. 예를들면 두 집합(bag of words라던가)간의 유사성 평가에 사용할 수 있음.

아래는 http://en.wikipedia.org/wiki/Locality-sensitive_hashing 에서 퍼온 내용. (ACM Communication에도 실려있음.)

Suppose is composed of subsets of some ground set of enumerable items and the similarity function of interest is the [[Jaccard index| Jaccard index]] . If is a permutation on the indices of , for let . Each possible choice of defines a single hash function mapping input sets to integers.

Define the function family to be the set of all such functions and let be the uniform distribution. Given two sets the event that corresponds exactly to the event that the minimizer of lies inside . As was chosen uniformly at random, and define an LSH scheme for the Jaccard index.

간단하게 예로 설명하자면.. 두개 집합 A={a, b, c, f, g} 와 B={b, c, h, j}가 있다고 하자. 이 두 집합에 대한 Jaccard Index를 계산하려면 공통된 pair를 일일히 봐야한다.

하지만 만약, random permutation 가 다음과 같이 정의되었다고 하자. . 그러면 집합 A에 대하여 이 permutation 를 대응 시킨 인덱스는 이고 B는 에 대해 가 된다. 따라서 가 된다.

주어진 하나에 대한 계산 방법은 위와 같고, 실제로는 를 uniform distribution에서 개 뽑은다음 를 만족하는 가 개 였다면, 는 Jaccard Index와 높은 확률로 같다고 판정한다.