地理情報システム特論第 12 回：時空間データ構造

.
.
.
..
.
.
.
地理情報システム特論
第 12 回：時空間データ構造
大沢裕
埼玉大学
.
Ohsawa (Saitama Univ.)
GIS-12
1 / 16
GIS-12
2 / 16
.
. .1 時間データベース
.
. .2 時空間データ管理構造
.
. .3 部分永続木
.
. .4 空間データにおける時間管理
.
Ohsawa (Saitama Univ.)
.
時間データベース
時間データベース
データベースで扱う時間
実在時間 (valid time)
オブジェクトが現実世界に実在していると認識されている時間
誤りが発見されたとき，過去に戻り修正する必要がある
登録時間 (transaction time)
あるオブジェクトをデータベースに登録した時間
時間経過とともに単調増加する
過去にさかのぼって修正されることはない
.
Ohsawa (Saitama Univ.)
GIS-12
3 / 16
時間データベース
時間データベースの分類
rollback database
過去のリレーションを蓄積する
トランザクション時間で索引づけられたスナップショットリレーショ
ンの系列
トランザクション時間を表すために，時間 ID(整数値) がふられる
histrical database
タプル毎に独立した更新の情報を記録する
DB の登録事項に変更があったとき，タプルの情報が修正される
上の性質により実在時間の管理が行え，登録時間の管理は行えない
temporal database
実在時間と登録時間を共に管理するデータベース
bi-temporal データベースとも呼ばれる
トランザクションの開始 (Ts)，終了 (Te)，実在時間の開始 (Vs)，終
了 (Ve) の 4 つの時間を管理する
.
Ohsawa (Saitama Univ.)
GIS-12
4 / 16
.
時空間データ管理構造
RT-tree
H.Xu et al.(1990)
時間と空間を分けて管理する
RT-tree のスロットは (S, T , P) を持つ
S ：通常の R 木と同じ，空間の MBR
T ：スロットの存在時間 [ti , tj )，但し (ti < tj )
P ：通常の R 木と同じ，エントリーへのポインタ
T の管理法
T = [ti , tj ) が tj+1 時間で変化がなかったら，T = [ti , tj+1 ) に修正する
もし変化があれば，新しいエントリーを作り，それに [tj+1 , Tj+1 ) を付
け，RT-tree に追加する
RT-tree は時間軸を分割する機能がないため，時間経過と共にエント
リー数が増加し，検索効率が低下する
.
Ohsawa (Saitama Univ.)
GIS-12
5 / 16
時空間データ管理構造
3D R 木
時間軸を空間軸と同様に扱う
MBR を扱う際に範囲が閉じて
いないと扱いにくい
空間軸は長さが布袋であるが，
時間軸は長さが増え続ける
Figure: 3D R-tree
.
Ohsawa (Saitama Univ.)
GIS-12
6 / 16
.
時空間データ管理構造
2+3R-tree
現在生きているオブジェクトは 2D R 木で管理する (前方 R 木)
消去されたオブジェクトは 3D R 木で管理する (後方 R 木)
前方 R 木から後方 R 木への移動
終了時間が確定したとき，3 次元空間中の線分を作る．
それを後方 R 木に投入する．
対応するエントリーを前方 R 木から取り除く．
.
Ohsawa (Saitama Univ.)
GIS-12
7 / 16
時空間データ管理構造
HR-tree
Nascimento らが提案 (1999)
ᩮࡁ࡯࠼ߩ㈩೉
データの移動が発生する都度新
しい版の R 木を作る
V
4
時間 t0 で初期版の R 木を作る
時間 tq で変化が生じたとき，
新しい R 木の根を作る．但し，
変化が生じなかった部分木へは
古い版をポインタで指し示す．
.
Ohsawa (Saitama Univ.)
GIS-12
#
ᤨ㑆⚻ㆊ
V
4
$
%
%
8 / 16
.
部分永続木
部分永続木 (1)
完全永続 (full persistence)：全ての版に対して更新可能
部分永続 (partial persistence)：最新版に対してのみ更新可能
Becker ら (1996) は，B+木を対象とた部分永続木を提案した．
B+木の各ノードは，次のレコードを持つ
¡キー，ts ,te , ポインタ¿
終了時間が確定していないエントリーは te の値として＊を持つ
.
Ohsawa (Saitama Univ.)
GIS-12
9 / 16
部分永続木
部分永続木 (2)
時刻 2 でエントリー 40 が追加された
時刻 3 でエントリー 65 が削除された
4
#
$
PFXGTUKQP
TFXGTUKQP
$
#
$
#
.
Ohsawa (Saitama Univ.)
GIS-12
10 / 16
.
部分永続木
部分永続木 (3)
時刻 4 で 35 が，時刻 5 で 15 が，時刻 6 で 30 が，時刻 7 で 25 が削
除された
その結果ノード A で現存するエントリーは 2 つに減った
4
#
$
$
#
.
Ohsawa (Saitama Univ.)
GIS-12
11 / 16
部分永続木
部分永続木 (4)
時刻 8 でデータ 5 が追加された
ノード A で生き残っているノードのみ集めたノード A’ を作る
ノード A は終了時間を確定させる（弱分割）
4
4
#
#
$
$
#̉
.
#
$
#
Ohsawa (Saitama Univ.)
GIS-12
#̉
$
12 / 16
.
部分永続木
部分永続木 (5)
時間 9 で 40 が削除された
その結果ノード A に生存しているデータは 1 つに減った
A を兄弟 B とマージする．そのページを 2 つに分割する (強分割)
4
4
#
#
$
$
%
&
$
#
.
$
#
%
&
Ohsawa (Saitama Univ.)
GIS-12
13 / 16
部分永続木
部分永続木 (6)
現在の値ノード R1 に新たなノード G が追加された
その結果根ノードは容量を超える
根ノードの弱分割を行う
5
5
5
$!
$!
(!
%!
%!
*!
&!
&!
'!
'!
(!
(!
)!
)!
*!
.
Ohsawa (Saitama Univ.)
GIS-12
14 / 16
.
部分永続木
部分永続木 (7)
現在の値ノード R1 に新たなノード G が追加された
その結果根ノードは容量を超える
この例では生きているノードが多数のため，強分割を行う．
その結果，木は 1 段成長する
4
4
4
4
#
$
%
4
&
'
(
4
#
&
$
)
%
(
)
.
Ohsawa (Saitama Univ.)
GIS-12
15 / 16
空間データにおける時間管理
HR+木
Tao ら (2001) は，部分永続木の考え方を空間データに拡張した．
データの挿入，オーバーフローへの対策で，空間データ独特の性質
への対策がとられている．
検索時に次の問題が生じる
新しいエントリーに旧いエントリーの MBR も記録しておく．指定さ
れた時間に合わせて，検索時に参照する MBR を決定する．この方法
は，ノードに記録すべき情報が増えるため，ノードにおける子ノード
数を減少させる問題が生じる．
幅優先探索を行う．即ち，検索の際に上位レベルのノードから幅優先
でたどり，一度訪れたノードを記録しておくことにより 2 回以上たど
らないようにする．例えばこの目的のためにヒープを使うことがで
きる．
負の ID を用いる．元のノードには正のポインタを，コピーされた
ノードには負のポインタを持たせることにより，冗長なノードへの訪
問を抑制する．
.
Ohsawa (Saitama Univ.)
GIS-12
16 / 16

Download Report