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

Question

KD-TreeとR-Treeの定義を見ました。彼らはほとんど同じであるように思えます。

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

Answer 1

Rツリー と kDツリー 同様のアイデアに基づいています（軸に合わせた領域に基づいたスペースパーティション）ですが、重要な違いは次のとおりです。

• ノードイン kdツリーは分離平面を表しますが、Rツリーのノードは境界ボックスを表します。
• kDツリーは、領域に空間全体を分割しますが、Rツリーは関心のあるポイントを含むスペースのサブセットのみを分割します。
• kDツリーは、r-Treeの領域がオーバーラップする場合があるのに対し、D-Treeは分離パーティション（ポイントは1つの領域のみに属します）を表します。

（分割スペースのための同様の種類のツリー構造がたくさんあります：Quadtree、BSP-Tree、r*-Treeなど）

Answer 2

実際にはまったく異なります。それらは同様の目的（空間データの領域クエリ）を提供し、どちらも木ですが、それは共通点があります。

• Rツリーはそうです バランスが取れています, 、KD-Treeは（バルクロードされていない限り）ではありません。これが、KD-Treeを再最適化するために再構築する必要があるため、データを変更するためにRツリーが好まれる理由です。
• Rツリーはそうです ディスク指向. 。実際に、ディスク上の表現に直接マッピングされる領域でデータを整理します。これにより、実際のデータベースやメモリ外の操作においてより有用になります。 KD-Treeはそうです メモリ指向 ディスクページに入れるのは自明ではありません
• Rツリーは、データ空間全体をカバーしていません。空の領域が発見される場合があります。 KD-Treesは常にスペース全体を覆っています。
• KD-Trees バイナリスプリット データ空間、Rツリーはデータを分割します 長方形. 。バイナリスプリットは明らかにばらばらです。 R-Treeの長方形は重複する場合があります（実際には良いこともありますが、重複を最小限に抑えようとします）
• KD-Treeはメモリで実装するのがはるかに簡単です。実際には重要な利点です
• Rツリーは保存できます 長方形とポリゴン, 、KD-Treesのみがポイントベクトルのみを保存します（ポリゴンにはオーバーラップが必要であるため）
• Rツリーには、さまざまな最適化戦略、さまざまなスプリット、バルクローダー、挿入および再挿入戦略などがあります。
• KD-Treesは、ユークリッド距離とMinkowskiの規範を四角にサポートしていますが、Rtreesは測地測定距離もサポートすることが示されています（Geodataの近くのポイントを見つけるため）。

Answer 3

言及されていない2つの間の大きな違い この答え KD-Treeは、バルクローディングの状況でのみ効率的であるということです。 KDツリーの構築、修正、またはリバランスを構築すると、自明ではありません。 Rツリーはこれに苦しんでいません。