Near duplicate documents 를 찾는 식 중에 Jaccard coefficient라는 것이 있습니다. 어떤 문서내 term id들이

T(d)

로 정의된다고 하면, Jaccard coefficient는

(T(d_1) \cap T(d_2)) / (T(d_1) \cup T(d_2))

로 정의됩니다. 즉 term이 몇개나 겹치나하는 것이죠.

이런 term의 겹침을 계산하는 방법 중 하나는 locality sensitive hashiing입니다. 위키의 식 중 하나를 인용해서 설명하면

Pr(h(a)=h(b)) = \phi(a,b)

가 localitiy sensitive hashing입니다. 즉, 어떤 해싱 함수를 써서 a와 b를 변환한다음 그 값이 같을 확률은 a와 b의 유사도와 같다라는 것입니다.

여기까지가 introduction이고 본문은 http://knol.google.com/k/simple-simhashing에 있습니다. 혹은 Soumen Chakrabarti, Mining the web, Morgan Kaufmann에도 설명되어있습니다. (좋은 책입니다.)

knol의 글에서는 여러번반복해서

((T(d_1) \cap T(d_2)) / (T(d_1) \cup T(d_2)))^n

을 구한다고 되어있는데, Mining the web에서는 m개의 hash function을 찾은다음 그 중에서 k회

h(a)=h(b)

가 성립하면

\phi(a,b)=k/m

으로 계산하고 있습니다.