問題タブ [kdtree]

多次元検索 (KDTree や RTree など) をサポートできるデータベース上に C++ アプリケーションを構築したいと考えています。R ツリーを有効にした SQLite は最大 5 次元しかサポートしていませんが、これは私が必要とするよりもはるかに小さいものです。なにか提案を？

約 100 万のドキュメントを含む MongoDB があります。これらのドキュメントにはすべて、次のような 1 と 0 の 256 ビット ビンを表す文字列があります。

0110101010101010110101010101

理想的には、バイナリに近い一致を照会したいと思います。これは、2 つのドキュメントに次の番号がある場合を意味します。はい、これがハミング距離です。

これは現在、Mongo ではサポートされていません。そのため、アプリケーション層でやることを余儀なくされています。

したがって、これを考慮して、ドキュメント間で個々のハミング距離を比較する必要がないようにする方法を見つけようとしています。そのため、これを行う時間が基本的に不可能になります。

私はたくさんのRAMを持っています。また、Ruby には、多数のツリーを作成できる優れた gem (アルゴリズム) があるようですが、作成する必要があるクエリの数を減らすような作業を (まだ) 行うことができないようです。

理想的には、100 万件のクエリを作成し、重複に近い文字列を見つけて、それを反映するように更新できるようにしたいと考えています。

誰の考えも大歓迎です。

線分のセットがあります。それらに対して次の操作を実行したい:

1. 新しい線分を挿入します。
2. 与えられた点の半径 R 内にあるすべての線分を見つけます。
3. 与えられた点の半径 R1 内にあるすべての点を見つけます。
4. 与えられた線分が既存の線分と交差するかどうかを調べます。正確な交点は必要ありません (ただし、おそらく何も単純化されません)。

問題は、kd/bd ツリーや BSP ツリーなどのアルゴリズムが静的なポイント セットを想定していることです。私の場合、ポイントは常に新しいポイントで拡張され、ツリーの再構築が必要になります。

この状況に最も適したデータ構造/アルゴリズムは何ですか?

編集：最も簡単で私の問題を解決する答えを受け入れました。みんな、ありがとう！

kdツリーを使用して2次元空間のポイントを検索するアプリを作成しています。開発中に、各ポイントを囲む最も近いゾーンを「見る」ことができれば便利です。

添付の画像では、赤い点はkdツリー内の点であり、各点を囲む青い線は、最近傍探索が含まれている点を返すゾーンを境界付けています。

画像は次のように作成されました。

このアルゴリズムには2つの問題があります。

• （より重要）私の（かなり速いCore i7）コンピューターでは遅いです。
• （それほど重要ではありません）青い線の幅が変化していることがわかるように、それはずさんです。

この一連のポイントの「視覚化」とは何ですか？

そのような視覚化を作成するためのいくつかの良いアルゴリズムは何ですか？

2D 二分探索木からノードを削除することについて、誰かが役立つ洞察を提供できるかどうか疑問に思っていました。

4 つのケースがあることは理解していますが、そのうちの最初のケースを完了しました。

1. 子を持たないノード (リーフ) を削除するには、単純に、そのノードへのポインターを null に設定するだけです。
2. 左側のノードに 1 つの子があり、右側のノードが null であるノードを削除します。
3. 右側のノードに 1 つの子があり、左側のノードが null であるノードを削除します。
4. 左右に 2 つの子を持つノードを削除します。

2、3、および 4 を正確に実行する方法がわかりません。繰り返し実行しようとしましたが、うまくいかないようです。これは再帰的に行う必要があると思います。これが正確にどのように行われるかについて、誰かが光を当てることができますか。これはJavaにありますが、問題ではありません:)

先日、kd-treesについて読んでいました。そのようなデータ構造が役立つ具体的で単純な状況を探していました。誰かそのような例を持っていますか？

基本的にデータベース内の float 型の 2 つの列である 2 つの値の範囲に基づいて、DB をクエリする必要があります。

いくつかの調査を行った後、次のいずれかを使用するアルゴリズムでこれを実装するオプションを絞り込みました。

1. 2D直交範囲検索
2. kd ツリー構造

データがクラスター化されているため、最初のオプションを削除しました。これは役に立ちません。

そのため、kd ツリー構造を使用する必要があります。しかし、どのように？私はそれをやったことがなく、どこから始めればよいかわかりません。この検索の結果を取得するためにスタブとして設定されたコントローラーの 1 つにメソッドがありますが、検索自体は実装されていません。

この機能の作成に関連する体系的な手順を取得しようとしています。これまでのところ、これは私が行う必要があると思っていたものですが、それが正しい方法であるかどうかはわかりません.

1. kd ツリーは、DB 内のデータからメモリ内に構築する必要があります。(しかし、これをいつ行うべきかはわかりません。Rails が起動したときか、リクエストが入ったときのどちらですか?)

2. データが更新されたら、ツリーを編集してツリー全体をデータベースに保存します

3. 明示的に構築せずに、DB自体にkdツリーのデータ構造を保存する方法はありますか?

また、私はグーグルで検索しましたが、誰かがこれに推奨できるリソースを持っているかどうか疑問に思っていますか?

私は、高次元の点（通常は〜11-13次元）に対して高速の最近傍（できればO（log n））を実行する方法を探しています。構造を初期化した後、挿入時に最適に動作するようにしたいと思います。KDツリーが頭に浮かびましたが、一括読み込みを行わずに動的挿入を行うと、kdツリーのバランスがとれなくなり、afaikのバランス調整はコストのかかる操作になります。

ですから、そのような設定にどのようなデータ構造を好むのか知りたいと思いました。高次元のポイントがあり、挿入を実行して最も近い隣人を照会したいとします。

私はDelaunay 三角形分割を研究しており(宿題ではありません)、次の問題について考えました:S平面上の点のセット (濃度がn) と三角形のセットT(濃度n-2が三角形のセットTは Delaunay 三角形分割を形成しDT(S)ますか?

最初の問題は、ドロネー三角形分割が一意ではないことです。そのため、ポイント セットを再構築して三角形セットと比較しても、答えが得られません。さらに、最適な Delaunay 三角形分割アルゴリズムを実装するのはかなり困難です (ただし、CGAL などのライブラリを使用することは問題ありませんでした)。

三角形集合が三角形分割であるかどうかをチェックする方法を知っていると仮定します (必ずしも Delaunay である必要はありません)。次に、Delanuay 三角形分割の定義を使用する必要があります。三角形分割のすべての三角形についてt、 の点はSの円周内に厳密にはありませんt。これにより、次の方法が得られます。

1. 些細なアプローチ。を反復しT、円周を計算して を反復しS、点が円周の内側にあるかどうかを確認します。ただし、これにはO(n^2)時間がかかり、最適とは言えません。
2. 魅惑のアプローチ。繰り返し、T円周を計算します。円周の内側にある点sは、円周の中心までの距離が半径よりも小さいことを意味します。上の最近傍探索構造を使用Sして、アルゴリズムを高速化します。たとえば、単純なkd ツリー構造からO(n log n)、平均的なアルゴリズムとO(n sqrt(n))最悪のケースのアルゴリズムが導き出されます。
3. もっと簡単なことを考えている人はいますか？

Tが三角形分割かどうかをチェックする問題に戻りましょう。の等価性や三角形の頂点のセットなどの些細な事前要件はS、 よりも速く実行できませんO(n log n)。残っていること — の 2 つの三角形ごとにT共通の面で交差するか、まったく交差しないかを確認します。

1. 繰り返しますが、交差をチェックしてTを何度も反復することでこれを行うことができますが、これはアルゴリズムです。TO(n^2)
2. t1«三角形とt2交差» の意味を考えてみましょう。それらのエッジが交差する場合、または 1 つの三角形が完全に別の三角形の中にある場合、それらは交差します。すべてのエッジを交差させる問題は、Bentley-Ottmann アルゴリズムO(n log n)を使用して一度に解決できます(最悪の場合は、は交差の数ですが、最初の交差が見つかった時点でアルゴリズムを停止できます)。また、ある三角形が別の三角形を完全に含む場合も認識していませんでしたが、Bentley-Ottmann アルゴリズムを修正して、セグメントではなくスイープ ラインと交差する三角形を維持できると信じています。ただし、実装は非常に複雑です。O((n + k) log n)kO(n log n)
3. 私は反復アルゴリズムについて考えました — 交差しない (またはエッジでのみ交差する) 三角形の構造を維持しましょう (kd-tree に非常に似たものにする必要があります)。次に、次の三角形 を追加しようとしますt。まず、tの頂点のいずれかが既に三角形の 1 つに含まれているかどうかを確認します。次に、交点が得られます。それ以外の場合は、構造に追加tします。ただし、検索してクエリを追加する時間が必要な場合はO(log n)、O(sqrt(n))この構造の高さのバランスを取る必要があります。これは、kd ツリーの場合でも困難です。

では、この問題の簡単な解決策を知っている人はいますか?

私は画像ライブラリを持っており、〜150の機能を持つ〜5000の画像があります。現在、約 300 の機能を持つ別の画像があり、ライブラリで最も類似した 5 つの画像を見つけたいと考えています。

ブルート フォースには約 300 * 5000 * 150 * 128 の操作が必要で、時間がかかりすぎます。そのため、ライブラリ内の各画像の機能用に kd ツリーを構築しました。これは、約 5000 kd ツリーを意味します。他のsiftライブラリが行ったように、近似最近傍のbbf検索を使用しました。しかし、パフォーマンスは、私の力ずくのアルゴリズムよりもさらに遅くなりました。私の実装のせいではないことを確認するために、他のライブラリのマッチングアルゴリズムを力ずくで修正したところ、それらのパフォーマンスも向上しました。

私の質問は、〜 5000 kd ツリーを 1 つのツリーに結合することは可能ですか? または、複数の画像を照合しながらパフォーマンスを向上させる他の方法はありますか?