AltaVista는 Jaccard 유사도를 스케치하여 거의 중복된 페이지를 찾아냈다

검색 엔진의 색인은 미러링되고 복사된 페이지로 가득 차 있으며, 이를 순진하게 중복 제거하려면 모든 페이지를 서로 비교해야 한다 — 수백만의 제곱.

브로더의 1997년 연구는 페이지를 shingle 집합으로 표현한 다음, 순열 하에서 가장 작은 해시를 가진 소수만 유지했다. 두 페이지의 집합은 Jaccard 유사도에 비례하여 최소값을 공유하므로, 짧은 스케치가 쌍별 비교 없이 유사도를 추정한다.

AltaVista는 이 스케치를 사용하여 웹의 거의 중복된 페이지들을 클러스터링하고 결과에서 복사본을 제거했다. 이 방법은 다루기 어려운 유사도 문제를 빠른 해싱 작업으로 바꿨다.

동일한 작은 해시는 페이지가 유사함을 의미한다

몇 개의 최소 해시가 요소별 비교 없이 Jaccard 유사도를 추정한다.

서명은 고정 크기이므로 페이지당 비용이 매우 작고 저장하기 좋다.

이는 편향되지 않은 추정량으로, 페이지 전반에 걸쳐 평균적으로 정확하다.

동일한 스케치가 대규모에서 거의 중복 감지와 클러스터링을 지원한다.

두 개의 큰 집합을 요소별로 비교하지 말라. 각각을 몇 개의 최소 해시로 축소하면, 그것들이 일치할 확률이 집합의 중첩과 같아지고 문제는 작아진다.

MinHash는 검색, 광고, 머신러닝에서 대규모 거의 중복 감지, 집합 유사도, 중복 제거의 기초가 되었으며, 이후 그 위에 구축된 지역성 민감 해싱 계열의 토대가 되었다.