computational-geometry - Locality Sensitive Hashing (LSH) の ε (イプシロン) パラメータとは何ですか?

Question

Locality Sensitive Hashing に関する元の論文を読みました。

複雑さはパラメータ ε の関数ですが、それが何であるかはわかりません。

その意味を教えてください。

Answer 1

ε は近似パラメータです。

LSH ( FLANNおよびkd-GeRaFとして) は、高次元データ用に設計されています。その空間では、k-NNはうまく機能しません。実際、次元の呪いのために、力ずくのように遅くなります。

そのため、近似 k-NN を解くことに焦点を当てます。私たちの論文の定義 1 を確認してください。これは基本的に、正確な隣人よりも (1 + ε) 離れた場所にあるおおよその隣人を返すことは問題ないと言っています。

以下の画像を確認してください。

ここで、正確な/近似NNを見つけることの意味がわかります。NNS (最近傍探索) の伝統的な問題では、正確な NN を見つけるよう求められます。現代の問題である近似 NNS では、(1+ε) 半径内に隣接するものを見つけるように求められます。したがって、正確な NN または近似 NN のいずれかが有効な答えになります。

したがって、高い確率で、LSH はその (1+ε) 半径内の NN を返します。ε = 0 の場合、正確な NN 問題を実際に解きます。