くさもち研究室生活ブログだったもの Locality-Sensitive Hashing
Locality-Sensitive Hashing [1] (以降、LSH)は，Indykらによって提案された最近接点探索の確率的な近似アルゴリズム． LSHはハッシュテーブルを用いることで高次元のデータセットでも最近接点探索を高速に実行する． ・ハッシュテーブル(hash table) キーと値の組（エントリと呼ぶ）を複数個格納し，キーに対応する値をすばやく参照するためのデータ構造． ・ハッシュ関数(hash function) あるデータが与えられた場合にそのデータを代表する数値を得る操作．または，その様な数値を得るための関数のこと． ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという． LSHの重要なポイントは，類似しているデータ間のハッシュ値は一致し，類似していいないデータ間のハッシュ値は異なるようなハッシュ関数を用いることにある． これにより，ハッシュテーブ
くさもち研究室生活ブログだったもの LSHの論文
鬱です． ゼミ前ってホントいやですね． Imagineも大規模アップデートでいろいろと追加・変更があったので， そろそろやりたい． なんだかんだであまりにもブランクあけすぎた（あれｗもしかして，一ヶ月オーバー？）ので， さっさと復帰したい． でも，ゼミ終わるまでは無理． というかゼミが無理ｗ 打ち合わせがもっと無理ｗ さて，研究の話． 論文の内容の概略． この論文で初めてLSHが提案された．たぶん． でも，LSH主体な訳ではなく， あくまでε-NNS(ε-approximate Nearest Neighbor Search) を解く提案手法の一部として紹介されている． この論文では，ε-NNSを解くために， ring-cover treesという新しいデータ構造を用いることで高速化を可能としている． 詳細は・・・しょーじきよくわかりません（ぉぃ まあ，でも実際これは概略さえ知ってればいい
くさもち研究室生活ブログだったもの LSHまとめ(1)
LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ． 近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること． つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ． 言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる． （実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる） LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く． そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題） LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く， クエリqと遠い位置にある点ではハッシュ値が一致する確率が低
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
