R木
R木（英: R-tree）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。
概要
[編集]R木は、階層的に入れ子になった相互に重なり合う最小外接矩形 (MBR) で空間を分割する。R木のRは矩形 (Rectangle) を意味する。
R木の各ノードのエントリ数は可変である（事前に定義された上限がある）。葉ノード以外の各エントリには2つのデータが格納される。1つは子ノードへの参照であり、もう1つはその子ノードの全エントリを囲む外接矩形のデータである。
挿入および削除のアルゴリズムはこれらの外接矩形を使い、近い要素が同じ葉ノードに属するようにする（特に、新たな要素を挿入する際に、どの最下層の外接矩形にも収まらない場合、最も拡大が小さくて済む外接矩形に対応した葉ノードに属するようにする）。葉ノードの各エントリには2つのデータが格納される。1つは実際のデータ要素への参照であり（参照ではなく、葉ノード内に直接データ要素が格納される場合もある）、もう1つはそのデータ要素を囲む外接矩形のデータである。
同様に、探索アルゴリズム（例えば、共通部分、包含、最近傍）は外接矩形を使い、子ノードに対応する外接矩形内を探索すべきかどうかを判断する。このようにすると、探索においてほとんどのノードを走査する必要がなくなる。B木と同様、R木もデータベースに適しており、必要なノードだけをメモリ上にロードして操作することができる。
ノードが一杯になったときのノード分割アルゴリズムはいくつかあり、その方式によってR木は2次R木と線形R木に分けられる。
R木はこれまで最悪実行時間を保証できないとされてきたが、実世界のデータでは一般によい性能を発揮する。しかし2004年にPR木（Priority R木）という新たなアルゴリズムが発表された。これは、従来のものと同程度に効率的であると同時に、最悪時の性能も最適化されている。
派生
[編集]- R*木
- R+木
- X tree
- Greene tree
- ヒルベルトR木
- PR木（Priority R木） - PR木は、要素のばらつきが一定のデータでは通常のR木と同程度の性能だが、より極端なデータでは非常によい性能を発揮する[1]。
アルゴリズム
[編集]探索
[編集]入力は探索矩形（クエリボックス）である。R木での探索はB木での探索によく似ている。探索は根ノードを始点とする。内部ノードには外接矩形とそれに対応した子ノードへのポインタがあり、葉ノードには空間オブジェクトの矩形がある。それぞれのノードにある矩形について、探索矩形と重なるかどうかを判断する。重なるなら、対応する子ノードについても探索を行う。探索はこのように再帰的に行われ、全ての重なりを持つノードが探索される。葉ノードに到達すると、そこに格納されている外接矩形についても同様の比較が行われ、対応する空間オブジェクトが探索矩形内にあるかどうか（探索結果に含められるか否か）が決定される。
挿入
[編集]オブジェクトを挿入するには、木を根ノードから再帰的に走査する必要がある。その時点の内部ノード配下の全ての矩形を調べる。新たなオブジェクトを含めるのに拡大が最小で済む矩形を選択する。この選択基準に適合する矩形が複数存在する場合、元々の領域が小さい方を選択する。この選択を再帰的に繰り返していく。葉ノードに到達したら、葉ノードに空きエントリがあれば、そのまま挿入すればよい。葉ノードに空きがない場合、挿入する前にノードの分割を行う。R木でのノード分割アルゴリズムはいくつか存在する。
全体ロード
[編集]- Sort-Tile-Recursive (STR)[2]
- Packed ヒルベルトR木 - ノードを矩形の中心のヒルベルト値を使ってソートし、再帰的に木構造を構築する。
- Nearest-X - X座標の値に従って矩形をソートし、ノードを生成する。
脚注
[編集]- ^ Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: The Priority RTree: A Practically Efficient and WorstCase Optimal RTree
- ^ Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing
参考文献
[編集]- Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8
- Lars Arge, Mark de Berg, Herman J.Haverkort, Ke Yi: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, Proc. 2004 ACM SIGMOD international conference on Management of data, pp. 347-358. ISBN 1-58113-859-8
- Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer, 2005. ISBN 1-85233-977-2
- N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
