Loading article…
Rツリーは、空間アクセス方法、つまり地理座標、矩形、多角形などの多次元情報をインデックス化するために使用されるツリーデータ構造です。Rツリーは1984年にアントニン・グットマンによって提案され[ 2 ]、理論的および応用的な両方の文脈で広く使用されています[ 3 ]。Rツリーの一般的な実用例としては、レストランの場所や、典型的な地図を構成する多角形（道路、建物、湖の輪郭、海岸線など）といった空間オブジェクトを格納し、「現在位置から2km以内のすべての博物館を探す」、「現在位置から2km以内のすべての道路セグメントを取得する」（ナビゲーションシステムに表示するため）、「最寄りのガソリンスタンドを探す」（道路は考慮しない）などのクエリに対する回答を迅速に見つけることが挙げられます。Rツリーは、大円距離[ 5 ]を含むさまざまな距離指標の最近傍検索[ 4 ]を高速化することもできます。
このデータ構造の重要な考え方は、近接するオブジェクトをグループ化し、ツリーの次の上位レベルでそれらを最小境界矩形で表現することです。Rツリーの「R」は矩形を意味します。すべてのオブジェクトはこの境界矩形内に存在するため、境界矩形と交差しないクエリは、含まれるオブジェクトとも交差しません。リーフレベルでは、各矩形は単一のオブジェクトを表します。上位レベルでは、集約に含まれるオブジェクトの数が増加します。これは、データセットの粗い近似として捉えることもできます。
Bツリーと同様に、Rツリーもバランスのとれた検索ツリー（すべてのリーフノードが同じ深さにある）であり、データをページに整理し、ディスクへの保存用に設計されています（データベースで使用されているように）。各ページには最大エントリ数があり、これはしばしば次のように表されます。また、ルートノードを除き、最小限の充填率を保証しますが、最大エントリ数の30%～40%の最小充填率で最高のパフォーマンスが得られています（Bツリーは50%のページ充填率を保証し、B*ツリーは66%まで保証します）。これは、Bツリーに格納される線形データとは異なり、空間データにはより複雑なバランス調整が必要となるためです。
ほとんどのツリーと同様に、検索アルゴリズム（交差、包含、最近傍検索など）は非常に単純です。重要なアイデアは、境界ボックスを使用してサブツリー内を検索するかどうかを決定することです。このようにして、検索中にツリー内のほとんどのノードが読み込まれることはありません。Bツリーと同様に、Rツリーは、必要に応じてノードをメモリにページングでき、ツリー全体をメインメモリに保持できない大規模なデータセットやデータベースに適しています。データがメモリに収まる（またはキャッシュされる）場合でも、オブジェクトの数が数百を超えると、ほとんどの実用的なアプリケーションでは、すべてのオブジェクトを単純にチェックするよりもRツリーの方がパフォーマンス上の利点があります。ただし、インメモリアプリケーションには、わずかに優れたパフォーマンスを提供したり、実装がより簡単になる同様の代替手段があります。コンピューティングノードがネットワークで接続されているコンピュータクラスタでRツリーのインメモリコンピューティングを維持するために、研究者は分散環境でRツリーの下でデータ集約型アプリケーションを実装するためにRDMA（Remote Direct Memory Access）を使用しました。[ 6 ]このアプローチは、ますます大規模になるアプリケーションにも拡張可能であり、Rツリーに対して高いスループットと低いレイテンシのパフォーマンスを実現します。
Rツリーの主な難しさは、一方ではバランスが取れていて（つまり、リーフノードの高さが同じ）、他方では矩形が空きスペースをあまり占めず、あまり重なり合わない（つまり、検索時に処理する必要のあるサブツリーの数が少なくなる）効率的なツリーを構築することです。たとえば、効率的なツリーを得るために要素を挿入する元のアイデアは、境界ボックスの拡大が最小限で済むサブツリーに常に挿入することです。そのページがいっぱいになると、データはそれぞれ最小領域をカバーする2つのセットに分割されます。Rツリーの研究と改良のほとんどは、ツリーの構築方法を改善することを目的としており、効率的なツリーをゼロから構築すること（バルクロードとして知られています）と、既存のツリーに変更を加えること（挿入と削除）の2つの目標に分類できます。
Rツリーは最悪ケースでのパフォーマンスを保証するものではありませんが、実世界のデータでは一般的に良好なパフォーマンスを発揮します。[ 7 ] Rツリーの（バルクロードされた）優先度Rツリーのバリアントは最悪ケースで最適ですが、[ 8 ]複雑さが増すため、理論的な研究にとどまり、実用的なアプリケーションではあまり注目されていません。
データが R ツリーに整理されている場合、空間結合を使用して、すべての点の指定された距離 r 内の近傍とk 個の最近傍(任意のL p -ノルムの場合) を効率的に計算できます。 [ 9 ] [ 10 ]これは、たとえばローカル外れ値因子など、このようなクエリに基づく多くのアルゴリズムに有益です。DeLi-Clu、[ 11 ] Density-Link-Clustering は、同様の種類の空間結合に R ツリー構造を使用してOPTICSクラスタリングを効率的に計算するクラスタ分析アルゴリズムです。
Rツリーのデータはページ単位で整理され、各ページには可変数のエントリ（事前に定義された最大値まで、通常は最小充填数以上）を含めることができます。非リーフノード内の各エントリには、子ノードを識別する方法と、この子ノード内のすべてのエントリの境界ボックスという2つのデータが格納されます。リーフノードには、各子に必要なデータが格納されます。多くの場合、子を表す点または境界ボックスと、子の外部識別子です。点データの場合、リーフエントリは点そのものになります。ポリゴンデータ（多くの場合、大きなポリゴンを格納する必要があります）の場合、一般的な設定では、ポリゴンの最小境界矩形（MBR）と一意の識別子のみをツリーに格納します。
Rツリーにおける検索プロセスは、フィルタリングと精緻化の原則（FRP）に沿った2段階のアプローチを採用しています。この構造では、内部ノードがクエリと交差しない空間領域を迅速に除外することで初期フィルタとして機能し、一方、リーフノードは実際の空間オブジェクトを格納することで、より精緻で正確な評価を提供します。
具体的には、範囲検索では、入力は検索矩形（クエリボックス）です。検索は、B+ツリーの検索と非常によく似ています。検索はツリーのルートノードから始まります。すべての内部ノードには、矩形のセットと対応する子ノードへのポインタが含まれており、すべてのリーフノードには空間オブジェクトの矩形が含まれています（空間オブジェクトへのポインタが含まれている場合もあります）。ノード内のすべての矩形について、検索矩形と重なるかどうかを判定する必要があります。重なる場合は、対応する子ノードも検索する必要があります。このようにして、重なるすべてのノードが走査されるまで再帰的に検索が行われます。リーフノードに到達すると、含まれている境界ボックス（矩形）が検索矩形に対してテストされ、オブジェクト（存在する場合）が検索矩形内にある場合は、結果セットに追加されます。
最近傍検索などの優先度検索の場合、クエリは点または矩形で構成されます。ルートノードが優先度キューに挿入されます。キューが空になるか、必要な数の結果が返されるまで、キュー内の最も近いエントリを処理することで検索が続行されます。ツリーノードが展開され、その子が再挿入されます。キュー内で葉エントリが見つかると返されます。[ 12 ]このアプローチは、地理データに対する大円距離など、さまざまな距離メトリックで使用できます。[ 5 ]
オブジェクトを挿入するには、ルートノードからツリーを再帰的にたどります。各ステップで、現在のディレクトリノード内のすべての矩形が調べられ、拡大が最小限で済む矩形を選択するなどのヒューリスティックを使用して候補が選択されます。次に、検索はこのページに降りていき、リーフノードに到達します。リーフノードがいっぱいの場合、挿入を行う前に分割する必要があります。ここでも、網羅的な検索はコストが高すぎるため、ヒューリスティックを使用してノードを 2 つに分割します。新しく作成されたノードを前のレベルに追加すると、このレベルが再びオーバーフローする可能性があり、これらのオーバーフローはルートノードまで伝播する可能性があります。このノードもオーバーフローすると、新しいルートノードが作成され、ツリーの高さが増加します。
アルゴリズムは、どのサブツリーに挿入するかを決定する必要があります。データオブジェクトが単一の矩形に完全に含まれている場合は、選択は明確です。複数の選択肢がある場合、または拡張が必要な矩形がある場合は、選択がツリーのパフォーマンスに大きな影響を与える可能性があります。
オブジェクトは、拡大が最も少ないサブツリーに挿入されます。全体を通して混合ヒューリスティックが使用されます。次に、オーバーラップを最小化しようとします（同点の場合は、拡大が最も少ないものを優先し、次に面積が最も小さいものを優先します）。上位レベルでは、Rツリーと同様の動作をしますが、同点の場合は再び面積の小さいサブツリーを優先します。R *ツリーにおける矩形のオーバーラップの減少は、従来のRツリーに対する主要な利点の1つです。
ノードのすべてのオブジェクトを 2 つのノードに再分配する方法は指数関数的に多くの選択肢があるため、最適な分割を見つけるにはヒューリスティックを使用する必要があります。古典的な R ツリーでは、Guttman は QuadraticSplit と LinearSplit という 2 つのヒューリスティックを提案しました。 Quadratic Split では、アルゴリズムは同じノードに存在する最悪の組み合わせとなる長方形のペアを探し、それらを 2 つの新しいグループの初期オブジェクトとして配置します。次に、いずれかのグループに対する優先順位が最も高いエントリ (面積の増加に関して) を探し、すべてのオブジェクトが割り当てられるまで (最小充填を満たすまで)、そのオブジェクトをこのグループに割り当てます。
他にも、Greene の分割[ 13 ]、 R *-tree分割ヒューリスティック[ 14 ] (これも重複を最小限に抑えようとしますが、二次ページを好みます)、Ang と Tan が提案した線形分割アルゴリズム [ 15 ] (ただし、非常に不規則な長方形を生成する可能性があり、多くの実際の範囲クエリやウィンドウクエリのパフォーマンスが低下します) などの分割戦略があります。R *-tree は、より高度な分割ヒューリスティックに加えて、ノード メンバーの一部を再挿入することでノードの分割を回避しようとします。これは、 B-tree がオーバーフローしたノードのバランスを取る方法に似ています。これにより重複が減り、ツリーのパフォーマンスが向上することも示されています。
最後に、Xツリー[ 16 ]は、R*ツリーの変種と見なすことができ、適切な分割が見つからない場合（特に高次元データの場合）、ノードを分割せず、すべての追加エントリを含むいわゆるスーパーノードを構築することも決定できます。
ページからエントリを削除すると、親ページの境界矩形を更新する必要がある場合があります。ただし、ページが不足している場合、隣接するページとのバランスは取られません。代わりに、ページは削除され、すべての子要素（葉ノードだけでなく、サブツリーも含む）が再挿入されます。この処理中にルートノードに要素が1つしかない場合、ツリーの高さが減少する可能性があります。
{{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク)
ウィキメディア・コモンズにあるRツリー関連のメディア