局所性鋭敏型ハッシュ
局所性鋭敏型ハッシュ(きょくしょせいえいびんがたハッシュ、英語: locality sensitive hashing)とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。
ハッシュ関数 h a , b ( υ ) : R d → N {\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}} を d {\displaystyle d} 次元のベクトル v {\displaystyle v} を整数の集合に移すような関数であると定義する。ハッシュ関数 h {\displaystyle h} は2つの乱数 a , b {\displaystyle a,b} によって定義される。ここで a {\displaystyle a} とは安定分布から独立に選ばれる乱数であり、 b {\displaystyle b} とは [ 0 , r ] {\displaystyle [0,r]} から一様に選ばれる実乱数である。