範囲検索用のデータ構造を探しています。範囲ツリーは適切な時間の複雑さを提供すると思います (ただし、いくつかのストレージ要件があります)。
ただし、範囲ツリーよりも、 KD ツリーなどの他のデータ構造の方が議論され、推奨されているように思えます。これは本当ですか？もしそうなら、なぜですか？
2 に答える
1
ポイント以外のオブジェクトを含むように kd-trees を簡単に拡張できるためだと思います。これにより、三角形の迅速なクエリが必要な仮想世界などで多くのアプリケーションが提供されます。範囲ツリーの同様の拡張は簡単ではありません。実際、私は見たことがありません。
簡単に要約すると、kd ツリーは、d 空間の n 個のポイントのセットを O(n log n) 時間で O(n) 空間を使用して構造に前処理できるため、任意の d 次元範囲クエリに答えることができます。 O(n 1-1/d + k) 時間で、k は回答の数です。範囲ツリーは、前処理に O(n log d-1 n) 時間、O(n log d-1 n) スペースを必要とし、O(log d-1 n + k) 時間で範囲クエリに答えることができます。
2 次元または 3 次元空間について話している場合、レンジ ツリーのクエリ時間は明らかに kd ツリーのクエリ時間よりもはるかに優れています。ただし、kd ツリーにはいくつかの利点があります。まず第一に、常に線形ストレージのみが必要です。第二に、それは常に O(n log n) 時間で構築されます。第 3 に、次元が非常に高い場合、ポイント セットが非常に大きくない限り、レンジ ツリーよりも優れたパフォーマンスを発揮します (ただし、この時点では、線形検索はほぼ kd ツリーと同じくらい高速になります)。
もう 1 つの重要な点は、レンジ ツリーよりも kd ツリーの方がよく知られていることです。計算幾何学のコースを受講するまで、範囲木について聞いたことはありませんでしたが、kd-trees については聞いたことがあり、それを使用したこともありました (コンピュータ グラフィックスの設定ではありましたが)。
編集: 何百万ものポイントがある場合、2D または 3D の固定半径検索に適したデータ構造は何かと尋ねます。私は本当にあなたに言うことはできません！多くのクエリを実行するとレンジ ツリーの方が高速になると言いたいところですが、3D の場合、構築は O(log n) 倍遅くなり、速度よりも先にメモリ使用量が問題になる可能性があります。両方の構造の優れた実装を統合し、特定の要件に対して何がより効果的かを単純にテストすることをお勧めします。
于 2015-04-18T14:09:47.520 に答える
0
ニーズ (2D または 3D での粒子シミュレーション) のために、すべての最近傍クエリが可能なデータ構造が必要です。カバー ツリーは、このタスクに最適なデータ構造です。カーネル密度推定のために最近傍を計算しているときに、これに遭遇しました。このウィキペディアのページではツリーの基本的な定義が説明されており、 John Langford のページには C++ 実装へのリンクがあります。
1 つのクエリの実行時間は O(c^12*logn) です。ここで、c はデータセットの拡張定数です。これは上限です。実際には、データ構造は他のデータ構造よりも高速に実行されます。この論文では、粒子シミュレーションに必要なすべての最近傍 (すべてのデータ ポイント) のバッチ処理の実行時間は O(c^16*n) であり、この理論上の線形境界はニーズに対しても実用的であることを示しています。 . 構築時間は O(nlogn) で、ストレージは O(n) です。
于 2015-04-20T11:40:05.303 に答える