進捗報告
論文
Relaxed Space Bounding for Moving Objects:
A Case for the Buddy Tree
SIGMOD Record 2006
S. Guo, Z. Huang, H. V. Jagadish, B. C. Ooi, Z. Zhang
National University of Singapore, University of Michigan
1
更新管理に求められる木構造性質
提案
k-d木 MD木
MDF木 R木
1. 領域分割
更新の高速化
2. 削除が容易
更新の高速化
3. 削除後の安定性
メモリの効率化、管理領域の適正
4. M分木である
更新・検索の高速化(メモリアクセスの削減)
5. 領域の重なりがない
検索の高速化
6. 木がバランスする
検索平均速度の高速・安定化
2
基本的な考え方
k-d木をバランスM分木に
◎重要度の高い分割軸に着目し、木を成長させる
着目点:
重要度 高
重要度が高いほど、木に
与える影響力が大きい
重要度が近いほど、領域
統合が容易
重要度 中
重要度 中
重要度 低
3
構成
ノード Node
子ノード数
管理領域
子ポインタ
重要分割軸
int n
Rect rec[M]
*Node child[M]
int critical_line (グループを分ける識別子)
critical_line
R2
R1
R4
Node
R3
R1 R4 R5 R3 R2
R5
4
ノード分割
critical_line
R1
R2
Node
R6
R4
R3
R1 R4 R5 R3 R2
R5
R6
critical_lineによって二つに分ける
A1
A2
critical_line
A1
分割を行ったら、子ノード
のcritical_lineを決定
critical_line
R1 R6
A2
critical_line
R4
R2
R5 R3
5
Critical_lineの決め方
y
R2
R1
R4
(x1, y1)
R3
R1
(x2, y2)
R5
R1 R2 R3 R4 R5
x
1. 外枠以外の辺について、x1どうし、y1どうし、x2どうし、y2どう
しが等しい長方形でグループを作る
2. グループ共通辺の長さが外枠の一辺の長さと等しいとき、そ
れをcritical_lineとする(ひとつでも見つかれば終了)
(例)上の図において、R1とR4はx2が共通でグループを形成し、
その辺の長さは外枠の一辺と等しく、critical_lineとなる 6
ノード統合
(例1)R3の削除・統合を考える
critical_line
R1
R2
A1
R6
R3
R4
A1
critical_line
A2
critical_line
R5
R7
R1 R6
R4
R2
R5 R7 R3
A2
1. グループ内でR3と辺を共有し、かつその辺の長さがR3以下
の長方形をすべて挙げる(ここではR7)
2. 対象長方形の共有辺をR3を含むように拡大(R7.y1をR3.y1
とする)
3. R3のデータを対象長方形に割り振り、終了
7
ノード統合
(例1)R3の削除・統合を考える
critical_line
R1
R2
A1
R6
critical_line
R4
A1
R7
A2
critical_line
R5
R1 R6
R4
R2
R5 R7
A2
8
ノード統合
(例2)R2の削除・統合を考える
critical_line
R1
R2
A1
R6
R3
R4
A1
critical_line
A2
critical_line
R5
R7
R1 R6
R4
R2
R5 R7 R3
A2
1. R2はグループ長方形がないため、同一Node内から
critical_lineを共有する長方形を挙げる(ここではR3,R5)
2. 対象長方形の共有辺をR2を含むように拡大
3. Ceitical_lineを設定、R2データを対象長方形に割り振り、終了
9
ノード統合
(例2)R2の削除・統合を考える
critical_line
R1
R6
A1
R3
R5
R4
A1
R7
critical_line
R1 R6
A2
critical_line
R4
R3 R7
R5
A2
10
ノード統合
(例3)A1とA2の統合を考える
critical_line
R1
R2
A1
R5
critical_line
critical_line
R3
R4
A1
A2
R1 R5
R4
R2
R3
A2
A2内長方形数の減少時、A1との統合を試みる
1. A1の長方形を、A2を包括するように拡大
2. A2以下にあるデータをすべてA1に挿入
3. A2以下のノードとリーフを削除。もしNode1の管理するノード
数が1以下ならば、Node1を削除、終了
11
ノード統合
(例3)A1とA2の統合を考える
R1
R5
critical_line
R6
R1 R5 R6 R7 R4
R4
R7
12
提案手法の利点
1. R-treeに比べて、挿入時や検索時、critical_lineを
用いることで比較回数がおよそ半分になる
2. M分木にすることで、空間的な距離の近い長方形ど
うしで統合が可能
3. Quad-treeやBD-treeを用いた手法に比べて、動的
に分割軸を決定できるため、局所に集中するデータ
に対応できる
4. ノード内の長方形は空間的な距離が近いため、更
新を少ない処理で行える可能性がある
5. Critical_lineを決定するための処理は必要だが、そ
13
の分、分割時のグループ分けは容易となる
高効率化のために
1. 分割軸を補正する
14
挿入アルゴリズム
1. データをrootから挿入、リーフまでたどる
2. もしリーフに空きがあれば、データを挿入、終了
3. リーフを分割、criticalによって分けられるグループ
をそれぞれ二つの子ノードに分ける
4. グループ内でそれぞれcriticalを設定
5. 親ノードに空きがあれば挿入、終了
6. 親ノードに対して、必要であれば再帰的にノードの
分割を行う、終了
15
リーフ分割
1. 兄弟リーフ数が2以下ならば、対象リーフ内データ
をリーフ長方形の長軸に対してソートし、二つのリー
フとリーフ長方形に分けて親ノードに追加、終了
2. 兄弟リーフ数が3で分割が生じたとき、兄弟リーフ3
つのデータをすべて集めてソートし、二つのグルー
プにわける。さらにグループ内でソートし分割、計4
つのリーフにわけ、criticalを決定し、親ノードに追
加、終了
3. 兄弟リーフ数が4以上ならば、
16
ダウンロード

進捗状況と今後の予定