近似最近傍アルゴリズムの研究を行っています。
私は最近、KNN を妥当な速度で見つけるという素晴らしい仕事をするAnnoy Libraryを見つけました。より深い分析のために、ミートアップスライドをざっと読むことができます。
スライドを読んでソース コードを調べた後、このアルゴリズムが高次元データで KD-Tree よりもうまく機能する理由がわかりません。
KD-Tree は優れた NN アルゴリズムですが、高次元では総当たり検索 [O(n^2)] とほぼ同じ実行時間を達成するため、多くの隣接する葉をチェックする必要があります。
その理由は、高次元では、単位球の体積がかなり小さくなるためです (ここで見ることができます)。
私が Annoy ライブラリで見つけた唯一の違いは、一度に 1 つの次元を分割するのではなく、超平面を使用して空間を分割することです。
このアルゴリズムを分析して、KD-Tree よりもはるかに高速である理由を説明できる人はいますか?
Annoy のこのセクションを読んでください。
それはどのように機能しますか：
ランダム プロジェクションを使用し、ツリーを構築します。ツリーのすべての中間ノードで、空間を 2 つの部分空間に分割するランダムな超平面が選択されます。この超平面は、サブセットから 2 つの点をサンプリングし、それらから等距離にある超平面を取得することによって選択されます。
これを k 回行うと、木の森ができあがります。k は、精度とパフォーマンスのトレードオフを調べて、必要に応じて調整する必要があります。
ここでの鍵は木の森だと思います。あなたは、かなり古いデータ構造であるKDツリーと比較しており、あなたが言ったように、次元の呪いに苦しんでいます。
ここでは、ランダム化された KD ツリーのフォレストを使用するのが適していると思います。
たとえば、私のkd-GeRaFはこれについて適切な説明を提供しています (論文を参照)。ただし、次元数が比較的小さい場合、つまり 100 程度の場合は、FLANNも興味深いものになるはずです。FLANN は kd-GeRaF よりも古いですが、多くの刺激を受けました。
コメントで示唆されているように、LSH が Annoy でどのように使用されているかはわかりませんが、そうであれば、RKD フォレストでは問題ありません。