©2024 Thoth Children All rights reserved.

R-Tree

ー 概要 ー

R-Treeは空間インデックスなどに使用される空間データや矩形情報などの多次元データを扱うツリー型データ構造.矩形データを近いもので集めてそれらの最小外接矩形を親ノードとしてつなげていく.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • 矩形や立方体のデータを複数持っている
効果
  • 高速に点の探索や領域範囲の探索を行うことができる
  • 近傍の矩形や立方体を集めその最小外接矩形を親ノードとして持つ木構造
  • 一定距離内の探索やk近傍の探索も高速
ポイント
  • 最悪計算時間を保証しないがリアルデータでは性能に問題ない
  • 全てのデータが同じ深さにある平衡木になっている
  • B-Treeを多次元に拡張したもので必要なデータのみを引っ張ればよくデータベースとの相性がよい
  • ノード同士が被らずまた最小外接矩形が空領域を含まないようにすると効率的
  • 親の持つ最大子ノード数をMとしてデータ数をNとすると探索時間計算量は、O(logM(n))

解 説

R-Treeは空間インデックスなどに使用される空間データや矩形情報などの多次元データを扱うツリー型データ構造. 矩形データ(2次元の場合)やポリゴンデータ(3次元の場合)を近いもので集めてそれらの最小外接矩形(Minimum Bounding Box)を親ノードとしてつなげていく.葉を除いた全ノードが最小外接矩形(Minimum Bounding Box)となっている.
R-Treeとは
R-Treeのデータ構造. 一番のルートは全領域を含み その下にR1,R2の最小外接矩形を持つ. 最終的にはR8~R19の実データを持つ. (画像はWikipediaより引用)
R-TreeはB-Treeを多次元に拡張したもので、 上図のように全てのデータが同じ高さにある平衡木になっており、 B-Treeがそうだったようにデータベースとの相性も良い. 必要なデータのみをデータベースより取り出せばよく探索のたびに全てを走査する必要はない. 各ノードは最大で持つ子の数が決まっており、その数をMとして、 データ数をNとすると、探索時間計算量はlogM(N)となっている. 探索や挿入は非常にシンプルな実装となる. アプリケーション ・ある点から一定距離内にあるデータを全て探す. ・ある矩形領域内にあるデータまたは重なっているデータを全て探す. ・近いものからk個のデータを探す.
R-Treeの特徴
この章を学んで新たに学べる
Comments

Reasons
>>隠す