KDD2015 Selective Hashing: Closing the Gap between Radius Search and k-NN Searchを読んだ
どんなもの?
k-NN用のHashを提案。LSHと同様のrecallを達成できることを示した
先行研究と比べると?
LSHは固定半径の近傍検索には向いているが、k-NNには向いていない。
k-NN向けのハッシュも存在しているが、グローバルな構造を見ている。
提案法は全ての点のローカルな構造を考慮している。
技術や手法のキモはどこ?
近傍の大きさを少しづつ大きくしたインデックスを作る
まわりのデータ密度に応じて各インデックスに登録する
マルチインデックスによる検索を行う
どうやって有効だと検証した?
- 理論的にLSHと同様のrecallを達成できることを証明
- 実データでrecallに対する検索時間やインデックスサイズの効率を示した
次に読むべき論文は?
- Similarity search in high dimensions via hashing
- Locality-sensitive hashing scheme based on p-stable distributions
- Lower bounds on locality sensitive hashing