Min-Hashing / LSH(Locality Sensitive Hashing)
100만개(10^6)의 문서에 대해 중복 검사한다고 해보자.이때 두 문서간 80%정도만 같으면 중복문서라고 가정한다. 가장 쉬우면서도 정확한 방법(Naive)으로는 두 문서를 뽑아서 Jaccard Similarity를 구하면 되는데, 두 문서의 비교작업만 5*10^11번 필요하고, 한 문서를 shingling한 dimention도 무시할 수 없으므로 time and space complexity 모두 어마어마한 작업이 된다. 참고로 Jaccard Similarity(Jaccard Index) 두셋(set)의 유사성을 표현하는 방법으로 (A,B의 교집합/A,B의 합집합) 으로 표현할 수 있다.A={1,2,3,4,5}B={1,3,5,7,9}교집합={1,3,5}합집합={1,2,3,4,5,7,9}J(A,B)=3..
더보기