くさもち研究室生活ブログだったもの LSHまとめ(1)LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ． 近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること． つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ． 言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる． （実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる） LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く． そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題） LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く， クエリqと遠い位置にある点ではハッシュ値が一致する確率が低
