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に対してすべてのハッシュ関数でハッシュ値を求める．

得られたハッシュと同じキーを持つエントリに含まれる特長ベクトルをすべて取り出す．（同じキーを持つエントリの和集合）→　最近接点候補

候補の中から最近接点を距離計算により発見．