서명을 만들고도 남는 탐색 비용
미니해시로 각 집합을 작게 요약하더라도 저장된 모든 서명을 매번 비교하면 항목 수에 비례하는 작업이 필요하다. LSH는 비슷할 가능성이 높은 후보만 먼저 모으는 색인을 덧붙인다. 요약의 크기를 줄이는 문제와 비교할 대상의 수를 줄이는 문제를 나누어 해결하는 것이다.
서명을 여러 밴드로 나누기
서명을 b개의 밴드로 나누고 각 밴드에 r개의 값을 넣는 방식을 생각할 수 있다. 대응하는 밴드의 값이 전부 같으면 두 집합을 후보로 연결한다. 어느 한 밴드에서라도 일치하면 후보가 되는 조건은 비슷한 집합이 여러 번 기회를 갖게 한다.
후보가 될 확률
독립적인 이상적 서명에서 자카드 유사도가 s이면 한 밴드가 전부 일치할 확률은 s의 r제곱이다. 모든 밴드가 불일치할 확률을 1에서 빼면 후보가 될 확률은 1-(1-s^r)^b가 된다. 예를 들어 s가 1/2이고 r과 b가 각각 2라면 후보 확률은 7/16이다.
문턱값은 절대적인 경계가 아니다
유사도가 기준보다 낮아도 후보에 들어올 수 있고 높아도 누락될 수 있다. 정확한 조건이 필요하면 후보의 원래 집합을 다시 비교해야 한다. 이 검사는 잘못 포함된 후보를 제거할 수 있지만 색인에서 이미 빠진 항목을 되찾아 주지는 않으므로 재현율도 함께 평가해야 한다.