R*ツリー

データ処理 において、R* ツリーは空間情報のインデックス作成に使用されるR ツリーの変種です。R* ツリーは、データの再挿入が必要になる可能性があるため、標準の R ツリーよりも構築コストがわずかに高くなりますが、結果として得られるツリーは通常、クエリのパフォーマンスが向上します。標準の R ツリーと同様に、ポイント データと空間データの両方を格納できます。1990 年に Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、および Bernhard Seegerによって提案されました。 ^[1]

カバレッジとオーバーラップの両方を最小限に抑えることは、R ツリーのパフォーマンスにとって重要です。オーバーラップとは、データのクエリまたは挿入時に、ツリーの複数のブランチを拡張する必要があることを意味します (データが重複する可能性のある領域に分割される方法のため)。カバレッジを最小限に抑えると、プルーニングのパフォーマンスが向上し、特に負の範囲のクエリの場合に、ページ全体を検索から除外する頻度が高くなります。R* ツリーは、改訂されたノード分割アルゴリズムとノード オーバーフロー時の強制再挿入の概念を組み合わせて、両方を削減しようとします。これは、R ツリー構造はエントリが挿入される順序に非常に左右されるため、挿入によって構築される (一括ロードではなく) 構造は最適ではない可能性が高いという観察に基づいています。エントリの削除と再挿入により、エントリはツリー内で元の位置よりも適切な場所を「見つける」ことができます。

ノードがオーバーフローすると、そのエントリの一部がノードから削除され、ツリーに再挿入されます。(後続のノード オーバーフローによって生じる無限の再挿入の連鎖を回避するために、再挿入ルーチンは、新しいエントリを 1 つ挿入するときにツリーの各レベルで 1 回だけ呼び出されます。) これにより、ノード内のエントリのよりよくクラスター化されたグループが生成され、ノードのカバレッジが削減されます。さらに、実際のノード分割は延期されることが多く、平均ノード占有率が上昇します。再挿入は、ノード オーバーフローでトリガーされる増分ツリー最適化の方法と見なすことができます。

R* ツリーは、分割の品質を定量化できる 3 つのメトリックを表します。これらは、2 つのクラスターの境界ボックスの交差領域として定義されるオーバーラップ (R* ツリーと R ツリーで共通)、2 つのクラスター境界ボックスの領域の合計であるエリア値、および 2 つのクラスター境界ボックスの周囲の合計であるマージン値です。

• 改良された分割ヒューリスティックにより、より長方形のページが生成され、多くのアプリケーションに適しています。
• 再挿入方法は既存のツリーを最適化しますが、複雑さが増します。
• ポイントデータと空間データを同時に効率的にサポートします。

• R* ツリーは、クエリおよび削除操作に通常のR ツリーと同じアルゴリズムを使用します。
• 挿入時に、R* ツリーは複合戦略を使用します。リーフ ノードでは重複が最小限に抑えられ、内部ノードでは拡大と領域が最小限に抑えられます。
• 分割する場合、R* ツリーは、周囲に基づいて分割軸を選択し、重複を最小限に抑えるトポロジカル分割を使用します。
• 改良された分割戦略に加えて、R* ツリーは、 B ツリーのバランスの概念に触発されて、オブジェクトとサブツリーをツリーに再挿入することで分割を回避しようとします。

したがって、最悪の場合のクエリと削除の複雑さは、R ツリーと同じです。R* ツリーへの挿入戦略は、R ツリーの線形分割戦略 ( ) よりも複雑ですが、オブジェクトのページ サイズに対する二次分割戦略 ( )ほど複雑ではなく、全体の複雑さにはほとんど影響しません。全体の挿入の複雑さは、依然として R ツリーと同程度です。再挿入はツリーの最大 1 つのブランチに影響するため、再挿入は通常の R ツリーで分割を実行するのと同程度です。したがって、全体として、R* ツリーの複雑さは通常の R ツリーと同じです。 ${\displaystyle {\mathcal {O}}(M\log M)}$${\displaystyle {\mathcal {O}}(M)}$${\displaystyle {\mathcal {O}}(M^{2})}$${\displaystyle M}$${\displaystyle {\mathcal {O}}(\log n)}$

完全なアルゴリズムの実装では、ここで説明されていない多くのコーナーケースや同点状況に対処する必要があります。

• ウィキメディア・コモンズの R*-tree に関連するメディア