91

KD-tree と R-tree の定義を見てみました。それらはほとんど同じであるように私には思えます。

KD ツリーと R ツリーの違いは何ですか?

4

3 に答える 3

116

それらは実際にはかなり異なります。これらは同様の目的 (空間データに対する領域クエリ) を提供し、どちらもツリーです (そして、両方ともバウンディング ボリューム階層インデックスのファミリーに属します) が、共通点はほぼそれだけです。

  • R ツリーはバランスが取れていますが、kd ツリーはそうではありません (一括ロードされていない場合)。これが、再最適化のために kd ツリーを再構築する必要がある場合があるため、データの変更に R ツリーが好まれる理由です。
  • R ツリーはディスク指向です。実際には、ディスク上の表現に直接マップされる領域にデータを編成します。これにより、実際のデータベースやメモリ不足の操作でより便利になります。kd ツリーはメモリ指向であり、ディスク ページに配置するのは簡単ではありません。
  • kd-trees は一括読み込み時にエレガントです (これを指摘してくれた SingleNegationElimination に敬意を表します)、R-trees はデータの変更に適しています (ただし、静的データで使用すると一括読み込みの恩恵を受けます)。
  • R ツリーは、データ空間全体をカバーするわけではありません。空き領域が表示される場合があります。kd-tree は常に空間全体をカバーします。
  • kd-treesバイナリはデータ空間を分割し、R-trees はデータを四角形に分割します。バイナリ分割は明らかにばらばらです。一方、R ツリーの四角形はオーバーラップする可能性があります (オーバーラップを最小限に抑えようとしますが、これは実際には良い場合もあります)。
  • kd-trees はメモリに実装するのがはるかに簡単です。これが実際に重要な利点です
  • R ツリーは四角形と多角形を格納できます。kd ツリーは点ベクトルのみを格納します (多角形にはオーバーラップが必要なため)。
  • R ツリーには、さまざまな最適化戦略、さまざまな分割、一括ローダー、挿入および再挿入戦略などが付属しています。
  • kd-trees は、分離する超平面までの 1 次元距離を境界として使用します。R ツリーは、バウンディングのために境界ハイパーレクタングルまでの d 次元の最小距離を使用します (真陽性をフィルタリングするために、一部のカウント クエリに最大距離を使用することもできます)。
  • kd ツリーは二乗ユークリッド距離とミンコフスキー ノルムをサポートしますが、R ツリーは測地距離もサポートすることが示されています (地理データの近くの点を見つけるため)。
于 2012-06-19T21:08:45.597 に答える
68

R ツリーとk d ツリーは同様のアイデア (軸に沿った領域に基づく空間分割) に基づいていますが、主な違いは次のとおりです。

  • k d ツリーのノードは分離面を表し、R ツリーのノードはバウンディング ボックスを表します。
  • k d ツリーは空間全体を領域に分割しますが、R ツリーは対象のポイントを含む空間のサブセットのみを分割します。
  • k d ツリーは互いに素なパーティション (点は 1 つの領域のみに属する) を表しますが、R ツリー内の領域は重複する場合があります。

(空間を分割するための同様の種類のツリー構造がたくさんあります: 四分木、BSP ツリー、R* ツリーなど)。

于 2010-12-03T12:58:32.930 に答える
43

この回答で言及されていない 2 つの主な違いは、KD ツリーは一括読み込みの状況でのみ効率的であることです。KD ツリーが構築されると、KD ツリーを変更または再調整することは簡単ではありません。R ツリーはこれに悩まされません。

于 2010-12-03T13:03:24.437 に答える