[CS246] Finding Similar Items (5) - LSH Family
Locality-Sensitive FamilyMeanings of Sensitivity Valuesfamily of $F$ of function은 다음을 만족하면 $(d_1, d_2, p_1, p_2)$-sensitive라고 부른다.모든 함수 $f \in F$와 점 $x,y$에 대하여 $d(x,y) \le d_1$이면, $f(x)=f(y)$일 확률은 최소 $p_1$이다.$d(x,y) \ge d_1$이면, $f(x)=f(y)$일 확률은 최대 $p_2$이다.$d$가 Jaccard distance라면 $d = 1-\text{sim}(x,y)$이므로$d(x,y) \le d_1 \Rightarrow 1 - \text{sim}(x, y) \le d_1 \Rightarrow 1 - d_1 \le \text{sim}(..
2023. 9. 22.
