Passion is like genius; a miracle.

Near duplicate documents 를 찾는 식 중에 Jaccard coefficient라는 것이 있습니다. 어떤 문서내 term id들이 로 정의된다고 하면, Jaccard coefficient는 로 정의됩니다. 즉 term이 몇개나 겹치나하는 것이죠.

이런 term의 겹침을 계산하는 방법 중 하나는 locality sensitive hashiing입니다. 위키의 식 중 하나를 인용해서 설명하면 가 localitiy sensitive hashing입니다. 즉, 어떤 해싱 함수를 써서 a와 b를 변환한다음 그 값이 같을 확률은 a와 b의 유사도와 같다라는 것입니다.

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

knol의 글에서는 여러번반복해서 을 구한다고 되어있는데, Mining the web에서는 m개의 hash function을 찾은다음 그 중에서 k회 가 성립하면 으로 계산하고 있습니다.