LoginSignup
2

More than 5 years have passed since last update.

Selective Hashing: Closing the Gap between Radius Search and k-NN Searchを読んだ

Posted at

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

ref

参考

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2