LSHアルゴリズム

基本的な考え方
対象となる特徴ベクトルp=(x1, ..., xd) (d：次元数) ↓ 二進数のベクトルv(p)に変換 v(p)=UnaryC(x1) ... UnaryC(xd) C：ベクトルの要素の最大値 UnaryC(x)：1がx個の列に0がC-x個の列をつなげた0,1で構成される値． ↓ ハッシュ関数：gI(p) {1, 2, ... , Cd}の部分集合Iによって選ばれたビットの値を並べた値がハッシュ値．

Step1:
{1, 2, ..., Cd}の部分集合Ii (i = 1, ..., L)について， のハッシュテーブルを作成．
(つまり，ひとつの特徴ベクトルにつきL回ハッシュ値を計算してテーブルに格納．)
全部でL個のハッシュテーブルTiができる．
このとき，競合(collision)する場合は，同じエントリに格納する．
ここ重要！ｍ9っ｀Д´) ﾋﾞｼｯ!!

Step2:
最近接点探索．
クエリqに対してすべてのハッシュ関数でハッシュ値を求める．
得られたハッシュと同じキーを持つエントリに含まれる特長ベクトルをすべて取り出す．（同じキーを持つエントリの和集合）→　最近接点候補
候補の中から最近接点を距離計算により発見．