LSHの論文

鬱です．
ゼミ前ってホントいやですね．

Imagineも大規模アップデートでいろいろと追加・変更があったので，
そろそろやりたい．
なんだかんだであまりにもブランクあけすぎた（あれｗもしかして，一ヶ月オーバー？）ので，
さっさと復帰したい．
でも，ゼミ終わるまでは無理．
というかゼミが無理ｗ
打ち合わせがもっと無理ｗ


さて，研究の話．
論文の内容の概略．

Approximate Nearest Neighbors: Towards Removing the Cures of Dimensionality

この論文で初めてLSHが提案された．たぶん．
でも，LSH主体な訳ではなく，
あくまでε-NNS(ε-approximate Nearest Neighbor Search)
を解く提案手法の一部として紹介されている．

この論文では，ε-NNSを解くために，
ring-cover treesという新しいデータ構造を用いることで高速化を可能としている．
詳細は・・・しょーじきよくわかりません（ぉぃ
まあ，でも実際これは概略さえ知ってればいいか思う．

しかしながら，ring-cover treesを構成する上でpoint location問題
を解く必要がある．
ここで，point location問題とは，queryの点が含まれている領域を探索すること．
http://www.cs.sunysb.edu/~algorith/files/point-location.shtml
で，論文では，point location問題の解法として，2つの手法を挙げており，
そのうちの片方がLSHというわけ．

あと，どうやらこの手法には次元の削減にramdom projection(ランダム射影)
を用いているらしい．
最初，ただランダムに次元を選ぶようなので，
まあ，そういうもんか
と思っていたら，きちんとした理論展開があるらしい・・・．
「Johnson-Lindenstrauss補題」というらしいけど，
どうやらこれも使ってるみたい．
一応，確認しておくか．