局所性鋭敏型ハッシュ
局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間 M = ( M , d ) {\displaystyle {\mathcal {M}}=(M,d)} と閾値 R > 0 {\displaystyle R>0} 、近似因子 c > 1 {\displaystyle c>1} によって定義される。LSH族は2点 p , q ∈ M {\displaystyle p,q\in {\mathcal {M}}} について次の2つの性質、
d ( p , q ) ≤ R {\displaystyle d(p,q)\leq R} ならば h ( p ) = h ( q ) {\displaystyle h(p)=h(q)} となる確率は P 1 {\displaystyle P_{1}\,} 以上である。
d ( p , q ) ≥ c R {\displaystyle d(p,q)\geq cR} ならば h ( p ) = h ( q ) {\displaystyle h(p)=h(q)} となる確率は P 2 {\displaystyle P_{2}\,} 以下である。
を満たす関数 h : M → S {\displaystyle h:{\mathcal {M}}\to S} により与えられる族であり, h {\displaystyle h} は F {\displaystyle {\mathcal {F}}} から一様乱数にしたがって選択される。