問題タブ [approximate-nn-searching]

特徴記述子 [SIFT、SURF など] を使用する場合 - 近似最近傍は画像間のマッチングを行うための最速の方法ですか?

100 次元空間に 500,000 点のデータベースがあり、最も近い 2 点を見つけたいと考えています。どうすればいいのですか？

更新: スペースはユークリッドです。申し訳ありません。そして、すべての答えに感謝します。ところで、これは宿題ではありません。

アイテムが 3 次元空間で別のアイテムに十分に近いかどうかを調べる STL マップを作成したいと考えています。これまでのところ、私の "less-than-functor" は非常にうまく機能しており、次のリンクに貼り付けられています。

現在、この問題は「最近傍」問題ではありません。むしろ「少し離れたところに隣人がいるか」という問題です。

私の例は、単一の次元を示しています。わかりやすくするために、Y/Z 寸法をスキップしました。

これまでの私の試み：

まれに、つまり、非常にまれですが、位置が重複している場合に、マップが一致するエントリを見つけられないことがあります。

まだSTLコンテナを使用していますが、これを実装するためにもっとうまくできることはありますか?

私は、128 次元記述子との特徴マッチングを実行するコードに取り組んでいます。

画像のすべての記述子は std::vector に格納されます。ここで InterestPoint には記述子ベクトルであるメンバー *double desc が含まれます。

次に、Flann マトリックスでこの構造を使用して、後で近似最近傍フィーチャ マッチングを実行します。これを次のように初期化します。

この flann::Matrix を ip1 ベクトルのすべての要素の *double desc メンバーで満たすにはどうすればよいですか? これは私が試したものです：

コンパイルしましたが、うまくいきませんでした。flann は、演算子 [] を使用して、flann::Matrix のすべての行にアクセスする方法を提供します。したがって、Matrix クラスは行優先です。

前もって感謝します、

私が解決しようとしている問題は、この質問で説明されています: O(1) でプレフィックス ツリーを使用して、単一の最近傍を検索しますか?

私の質問は、その質問ページの提案された解決策セクションに関するものです。そのセクションでは、ノードから開始してツリーをトラバースすることにより、各プレフィックス ツリーから最近傍を見つけることが言及されています。プレフィックスツリーにキーが存在するかどうかを調べるのは簡単ですが、最も類似したキーを取得することはまったくわかりません。これを達成する方法は？

誰かがこれを私に説明してくれたらいいのにと思いますが、グラフィックではない場合 (これが好ましいです)、少なくともいくつかの詳細を説明してください。

編集：

これが論文のコードです。これは Python で書かれていますが、残念ながら私は Python を使ったことがありません。誰かが python に精通していて、コードを検索して、プレフィックス ツリーを使用して最近傍を見つける方法を確認できる場合。https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

コースのスライドから、次のことがわかりました。

R^D のセット P とクエリ ポイント q を考えると、NN は P のポイント p_0 です。

同様に、近似係数が 1 > ε > 0 の場合、ε-NN は p_0 であり、次のようになります。

(なぜ ε が 1 にならないのだろうか)。

KD ツリーを構築し、次のアルゴリズムを使用して NN を検索します。 これは、私の考えとテストの限りでは正しいです。

近似最近傍検索 (ANNS) を実行するには、上記のアルゴリズムをどのように変更すればよいですか?

私の考えでは、現在のベスト (リーフの更新部分) を ε で​​乗算し、残りのアルゴリズムはそのままにしておくことです。ただし、これが正しいかどうかはわかりません。誰か説明できますか？

PS - NN の検索の仕組みを理解しています。

Computer Science のサイトで質問したのに、何も得られなかったことに注意してください。

I have read few sources on VP-tree for similarity knn. No one wrote about adding an element to exists tree, which is required for maintenance. Explanation of adding element will be just great.

私は実際に高次元データ (〜 50.000-100.000 の機能) に取り組んでおり、最近傍検索を実行する必要があります。次元が大きくなるにつれて KD-Trees のパフォーマンスが低下することを知っています。また、一般に、すべての空間分割データ構造は、高次元データで徹底的な検索を実行する傾向があることも読みました。

さらに、考慮すべき重要な事実が 2 つあります (関連性の高い順に並べてあります)。

• 精度:最近隣を見つける必要があります (近似ではありません)。
• 速度:検索はできるだけ速くする必要があります。(データ構造を作成する時間はそれほど重要ではありません)。

そこで、次のことについてアドバイスが必要です。

1. k-NN を実行するためのデータ構造。
2. 可能な限り正確に設定して、aNN (近似最近傍) アプローチを使用する方が良い場合は?.

近似最近傍アルゴリズムの研究を行っています。

私は最近、KNN を妥当な速度で見つけるという素晴らしい仕事をするAnnoy Libraryを見つけました。より深い分析のために、ミートアップスライドをざっと読むことができます。

スライドを読んでソース コードを調べた後、このアルゴリズムが高次元データで KD-Tree よりもうまく機能する理由がわかりません。

KD-Tree は優れた NN アルゴリズムですが、高次元では総当たり検索 [O(n^2)] とほぼ同じ実行時間を達成するため、多くの隣接する葉をチェックする必要があります。

その理由は、高次元では、単位球の体積がかなり小さくなるためです (ここで見ることができます)。

私が Annoy ライブラリで見つけた唯一の違いは、一度に 1 つの次元を分割するのではなく、超平面を使用して空間を分割することです。

このアルゴリズムを分析して、KD-Tree よりもはるかに高速である理由を説明できる人はいますか?

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

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

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