問題タブ [kdtree]

Java で KDTree の実装を探しています。
Google 検索を行ったところ、結果はかなりでたらめに見えます。実際には多くの結果がありますが、それらはほとんどが 1 回限りの小さな実装であり、もう少し「生産価値」のあるものを見つけたいと思っています。Apache コレクションや .NET 用の優れた C5 コレクション ライブラリのようなものです。パブリック バグ トラッカーを表示して、最後の SVN コミットがいつ行われたかを確認できる場所。また、理想的な世界では、空間データ構造用の適切に設計された優れた API を見つけることができ、KDTree はそのライブラリの 1 つのクラスにすぎません。

このプロジェクトでは、2 次元または 3 次元でのみ作業します。ほとんどの場合、適切な最近傍の実装に関心があります。

必要な機能のみが必要な場合に、キーと値のペアを格納するために使用するデータ構造を決定しようとしています

• 挿入
• 調べる

具体的には、ペアを削除したり、キー/値/ペアを反復処理したりする必要はありません。

キーは整数タプルで、値はポインター (参照など) です。（多くの）オブジェクトに分散した数百万のペアのみを保存しています。

現在、私はどちらかを使用することを検討しています

• ハッシュテーブル
• kd ツリー
• bツリー

私は（挿入/検索時間のために）ハッシュテーブルに傾いていますO(1)が、自分の傾向を確認したかったのです。

どの構造（上記またはその他の構造）をお勧めしますか、またその理由は何ですか? ハッシュ テーブルを推奨する場合、オブジェクトごとに個別のテーブルを作成するか、単一のテーブルを作成してオブジェクトの ID をキー タプルの一部として使用する必要がありますか?

kd treesのウィキペディアのエントリでは、kd ツリーで最近傍検索を行うためのアルゴリズムが提示されています。私が理解していないのは、ステップ 3.2 の説明です。検索ポイントと現在のノードの分割座標の差が、検索ポイントの分割座標と現在のベストの差よりも大きいという理由だけで、より近いポイントがないことをどのように知ることができますか?

最近傍探索 2D の KD ツリーを使用した NN 探索のアニメーション

Nearest Neighbor (NN) アルゴリズムは、特定の入力ポイントに最も近いツリー内のポイントを見つけることを目的としています。この検索は、ツリー プロパティを使用して検索スペースの大部分をすばやく除外することで効率的に実行できます。kd ツリー内の最近傍の検索は、次のように進みます。

1. ルート ノードから始めて、検索ポイントが挿入された場合と同じ方法で、アルゴリズムは再帰的にツリーを下に移動します (つまり、ポイントが現在のノードよりも大きいか小さいかに応じて、右または左に移動します)。次元を分割します)。
2. アルゴリズムがリーフ ノードに到達すると、そのノード ポイントを「現在のベスト」として保存します。
3. アルゴリズムは、ツリーの再帰を巻き戻し、各ノードで次の手順を実行します。 1. 現在のノードが現在のベストよりも近い場合、それが現在のベストになります。2. アルゴリズムは、分割面の反対側に、現在の最適なポイントよりも検索ポイントに近いポイントがあるかどうかを確認します。概念的には、これは、現在の最も近い距離に等しい半径を持つ検索ポイントの周りの超球と分割超平面を交差させることによって行われます。超平面はすべて軸が揃っているため、これは単純な比較として実装され、検索ポイントと現在のノードの分割座標の差が、検索ポイントから現在のベストまでの距離 (全体の座標) より小さいかどうかを確認します。1. 超球が平面を横切る場合、平面の反対側により近い点がある可能性があるため、アルゴリズムは現在のノードからツリーの他のブランチを下に移動して、より近い点を探し、検索全体と同じ再帰プロセスに従います。 . 2. 超球が分割面と交差しない場合、アルゴリズムはツリーを上っていき、そのノードの反対側のブランチ全体が削除されます。
4. アルゴリズムがルート ノードのこのプロセスを終了すると、検索が完了します。

通常、このアルゴリズムでは、平方根の計算を避けるために、比較に二乗距離が使用されます。さらに、現在の最適距離の 2 乗を変数に保持して比較することで、計算を節約できます。

kd-treeで10次元データのk最近傍検索を実装する必要があります。

しかし、問題は、私のアルゴリズムが k=1 の場合は非常に高速ですが、k>1 (k=2,5,10,20,100) の場合は 2000 倍も遅くなることです。

これは kd ツリーの正常な動作ですか?

kd-tree（2D）クラスを拡張して、ノード（ポイント）を削除できるようにしたいと思います。この削除は、ツリーの大部分を再構築することなく実行する必要があります。これらのスライド、スライド13で説明されているアルゴリズムは、私が求めているもののようです。ただし、ノード削除アルゴリズムで使用されているスライド7にある「findmin（）」の説明を理解するのに問題があります。

質問

1. 最後から2番目の行の「i」はどういう意味ですか？（他の場所で参照されていないため、これは作成者による間違いかもしれませんか？）

2. 「whichAxis」とは正確には何ですか？最も近くになりたい分割超平面の深さですか？

3. 最小化する「minimum（）」とは何ですか？これは軸までの距離ですが、作者がポイントを最小化しているように見えますが、これは私には意味がありません。

現在、バランスの取れた KD ツリー(K=2)のすべてのノードの K Nearest Neighborを見つけようとしています。

私の実装は、ウィキペディアの記事のコードのバリエーションであり、任意のノードO(log N)の KNN を見つけるのはかなり高速です。

問題は、各ノードの KNN を見つける必要があるという事実にあります。 各ノードを反復処理して検索を実行すると、約 O(N log N) になります。

これを行うより効率的な方法はありますか？

KDツリーを使用してKNN検索を作成しようとしています。私はKDツリーをうまく形成することができます（または少なくとも、私はできると信じています！）。私の問題は、ポイントのリスト内のすべてのポイントに最も近い2つのネイバーを検索していることです。

それで、ポイントが実際にツリー内にある場合でも、KDツリーを使用してポイントに最も近いK個の近傍を見つける方法はありますか、またはポイントごとに個別のKDツリーを構築して、希望するポイントを除外する必要がありますか？検索するには？

私の実装言語はC++ですが、アルゴリズムまたは一般的なヘルプのいずれかを探しています。ありがとうございます。

ありがとう、スティーブン

共有メモリ マシンでの KD-Tree の実装はありますか?

ありがとう
アルマン。

一連のポイントを検索するためのkdツリーを構築しようとしていますが、ウィキペディアの記事での「中央値」の使用について混乱しています。使いやすさのために、ウィキペディアの記事では、kdツリー構築の擬似コードを次のように述べています。

ここで中央値を適用する「正しい」方法がよくわからないという理由だけで、「中央値を選択...」の行について混乱しています。

私の知る限り、奇数サイズの（ソートされた）数値リストの中央値は、中央の要素（5つのリストの場合、要素番号3、または標準のゼロベースの配列のインデックス2）であり、偶数サイズの配列の中央値は、2つの「中央」要素の合計を2で割ったものです（つまり、6つのリストの場合、中央値は要素3と4の合計です。ゼロの場合は2と3です。インデックス付き-2で割った値）。

ただし、ここでは明確なポイントのセットを使用しているため、その定義は機能しませんか？それでは、特に長さ2のリストの場合、偶数サイズの数値リストの正しい中央値をどのように選択するのでしょうか。

私はすべての助けに感謝します、ありがとう！

-スティーブン

私はレイトレーシングを行っており、アクセラレーション構造 (kd-tree、BVH など) を介して高速化したいと考えています。自分でコーディングしたくありません。私がこれまでに試したこと：

• kd-tree を pbrt からヤンクします。内部依存関係が非常に多いため、すべての pbrt をコードに取り込まないと成功しませんでした。

• CGAL の AABB ツリー。イライラすることに、これは交点のみを返すようです。ポイントがどの三角形から来たのかわからない場合、三角形に色を効率的に補間することはできません。「ポイント」の概念を色で拡張したいのですが、これはゼロから多くのテンプレート コードを作成しないと不可能のようです。

• 自分で書いています。さて、私は独自のグリッド アクセラレーション クラスを作成しました。これは動作しますが、厄介で非効率的です。

したがって、誰かがこの目的に使用できる簡単なライブラリを提案できれば、本当に感謝しています! 必要なのは、三角形のスープと光線を与え、最も近い交点を見つけて、その三角形のインデックスを返すことだけです。