LSH-2

LSH

간략한 과정을 쓰면 앞선 과정을 거쳐 나온 signature를 통해서
bucket으로 hashing 후 적어도 한번 같은 bucket에 들어간 쌍들을 Candidate-pair(후보 쌍)으로 등록하고 similarity threshold t를 넘는 쌍을 "유사하다"라고 정의한다.

Partition, Hash function

• Partiton: 행렬 M의 행을 r개의 열로 구성된 b개의 band로 분할

  

• Hash

  • 각 열에서 band에 포함된 부분을 k개의 bucket에 hsahing
  • K가 클수록 좋다
  • 각 밴드마다 다른 hash function을 사용해야한다
  • 같은 bucket에 적어도 한번 hash된 열의 쌍들을 후보쌍으로 등록
  • b와 r을 적절히 조절하여야한다
    • b가 커지면 많은 후보쌍이 생긴다
    • b가 작아지면 negative false의 가능성이 늘어난다.

Similarity threshold

• b=20, r=5인 상황에서 C1, C2의 유사도가 80%라면

  • 특정 band에서 C1, C2이 동일한 경우 => (0.8)^5
  • 20 개의 band에서 C1, C2이 동일하지 않을 경우 => (1-0.328)^20 ~= .00035 (false negative)

• C1, C2의 유사도를 40%로

  • 특정 band에서 C1, C2이 동일한 경우 => (0.4)^5
  • 20 개의 band에서 C1, C2이 적어도 한번 동일한 경우 => 1-(1-0.01)^20 < 0.2 (flase positive)

• threshold

우리가 원하는 것

1 band of 1 row (선형 그래프)

b bands of r Rows
s-curve f = 1 - (1 - s^r)^b (적어도 하나의 밴드가 일치할 확률)
t~= (1/b)^(1/r) 정도일 때 f의 값이 급격히 상승
b와 r을 적당히 조절해서 우리가 원하는 그래프와 비슷하게 나오도록