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補題」というらしいけど，

どうやらこれも使ってるみたい．

一応，確認しておくか．