.
.
.
..
.
.
.
地理情報システム特論
第 7 回：空間ジョイン
大沢 裕
埼玉大学
.
Ohsawa (Saitama Univ.)
GIS-7
1 / 21
GIS-7
2 / 21
.
. .1 空間ジョイン
.
. .2 空間ジョインのアルゴリズム
.
. .3 最近接ペア検索
距離ジョイン
.
Ohsawa (Saitama Univ.)
.
空間ジョイン
空間検索の種類
空間インデックスの探索コストでの分類
single scan query
範囲検索，k-NN 検索など
空間インデックスを一回たどれば終了
O(N) の検索コスト．eg. O(log N)
multiple-scan query
空間ジョイン検索
空間インデックスが複数回たどられる．
O(N) より大きな検索コスト．
.
Ohsawa (Saitama Univ.)
GIS-7
3 / 21
空間ジョイン
Join 演算
Ro
nF S = {t ∗ u : t ∈ R ∧ PF (t, u)}
Ro
nF S = σF (R × S)
但し，t ∗ u は要素を連結した全てのタプル集合を表わす（直積）．
PF (t, u) は結合条件 F を満たすとき真値を返す関数
空間演算の基本戦略
フィルタステップ：まず簡単な検査で対象を絞り込む
精査ステップ：条件を満たすか精査する
.
Ohsawa (Saitama Univ.)
GIS-7
4 / 21
.
空間ジョイン
GIS や LBS で必要となる空間ジョイン演算
距離ジョイン
M 個 (2 以上) の施設集合の中から，施設間の距離が小さい M 個の要
素からなるグループを探す．
旅行計画
現在地から採取目的地に達する途中で，あらかじめ与えられた M 個
の POI 集合の中から１つずつ選んで訪れる際に，経路長が最小の訪
れ方を探す．
MTNN 検索
現在地から，あらかじめ与えられた M 個の POI 集合の中から１つず
つ選んで訪れ，再び現在地に戻る際に経路長が最小となる訪れ方を
求める．
これらの検索は，各 POI 集合の要素数が全て N の場合を考えると，探索
する空間の大きさは，N M となる．従って，基本的な演算量は O(N M ) で
ある．
.
Ohsawa (Saitama Univ.)
GIS-7
5 / 21
空間ジョイン
オブジェクトの空間的関係
S
R
C
S
R
D
S
E
R
F
S
R
G
SR
H
covers(q,p)=covered(p,q)
contain(q,p)=inside(p,q)
(b) meet(q,p)
(c) overlap(q,p)
検索コストによる分類
(d) covers(q,p)
コスト大： disjoint
コスト中：meet, overlap,
inside
コスト小：equal, conver,
contain
(e) contain(q,p),inside(p,q)
equal(q,p)
Ohsawa (Saitama Univ.)
S
Eigenhofer(1991) は，空間的関
係を 8 種類に分類している
(a) disjoint(q,p)
.
R
GIS-7
6 / 21
.
空間ジョイン
空間ジョイン検索の分類
２つのデータセット A = {a1 , .., an } と B = {b1 , .., bm } を考える．また
Id(x) を要素 x の ID を得る関数，Mbr(x) をその MBR を得る関数とする．
Brinkoff 等 (1993) は次の３つの空間ジョイン検索を定義している．
1) MBR 空間ジョイン：Mbr (ai ) ∩ Mbr (bj ) ̸= ∅ である全てのペ
ア (Id(ai ), Id(bj )) を求める処理．
2) ID 空間ジョイン：ai ∩ bj ̸= ∅ を満たす全てのペア
(Id(ai ), Id(bj )) を求める処理．
3) オブジェクト空間ジョイン：ai ∩ bj ̸= ∅ を満たす ai ∩ bj を
求める処理．
.
Ohsawa (Saitama Univ.)
GIS-7
7 / 21
空間ジョイン
MBR による空間インデックスの枝刈り
目的とする関係
equal(p,q)
contains(p,q)
inside(p,q)
covers(p.mbr,q.mbr)
covers(q,p)
disjoint(p,q)
meet(p,q)
overlap(p,q)
.
Ohsawa (Saitama Univ.)
木構造中の MBR と検査を必要とする関係
equal(P.mbr,q.mbr) ∨ covers(P.mbr,q.mbr) ∨
contains(P.mbr,q.mbr)
contains(P.mbr,q.mbr)
overlap(P.mbr,q.mbr) ∨ covers(q.mbr,P.mbr) ∨
inside(P.mbr,q.mbr) ∨ equa;(P.mbr,q.mbr) ∨
covers(P.mbr,q.mbr) ∨ contains(P.mbr,q.mbr)
covers(P.mbr,q.mbr) vee contains(P.mbr,q.mbr)
overlap(P.mbr,q.mbr) ∨ covers(q.mbr,P.mbr) ∨
equal(P.mbr,q.mbr) ∨ covers(P.mbr,q.mbr) ∨
contains(P.mbr,q.mbr)
disjoint(P.mbr,q.mbr) ∨ meet(P.mbr,q.mbr) ∨
overlap(P.mbr,q.mbr) ∨ covers(P.mbr,q.mbr) ∨
contains(P.mbr,q.mbr)
meet(P.mbr,q.mbr) ∨ overlap(P.mbr,q.mb) ∨
covers(P.mbr,q.mbr) ∨ contains(P.mbr,q.mbr)
overlap(P.mbr,q.mbr) ∨ covers(P.mbr,q.mbr) ∨
contains(P.mbr,q.mbr)
GIS-7
8 / 21
.
空間ジョインのアルゴリズム
深さ優先探索による空間ジョイン
Algorithm 1 SpatialJoin(R,S)
Require: 2 つの R 木 (R と S) の高さは等しい
1: for all ES ∈ S do
2:
for all ER ∈ R with ER .rect ∩ ES .rect ̸= ∅ do
3:
if R が葉ノード then { その時，S もまた葉ノード }
4:
(ER , ES ) を出力する．
5:
else
6:
ReadPage(ER .ref); ReadPage(ES .ref)
7:
SpatialJoin(ER .ref,ES .ref)
8:
end if
9:
end for
10: end for
Brinkhoff ら (1993) のアルゴリズム
２つの R 木，R と S の高さは同じと仮定
空間ジョイン演算では R 木を何度もたどる必要があるため，LRU
バッファを利用する．
.
Ohsawa (Saitama Univ.)
GIS-7
9 / 21
空間ジョインのアルゴリズム
平面操作を用いた CPU コストのチューニング
2 つのノード R と S 中のエントリーを，それぞれ左端の x 座標値で
ソートし，かつ平面操作により x 座標値が小さいものから重なりを
調べることにより，重なりを検査する回数を減らすことができる．
注目要素を t として，他の側の要素との比較を行う．
;
t の値
r1
s1
r2
s2
r3
U
T
U
U
T
T
:
.
Ohsawa (Saitama Univ.)
GIS-7
比較テストの対象
r1 ↔ s1
s1 ↔ r2
r2 ↔ s2 , r2 ↔ s3
r3 ↔ s3
10 / 21
.
空間ジョインのアルゴリズム
I/O 時間のチューニング
ReadPage 回数を減らしたい平面走査法により読み込まれる順序 (a) と (b) における位置
の差で順序が変わる
T
T
U
T
U
T
U
T
T
T
C
s1,r2,r1,s2,r3,r4
r1,s2,s1,r2,s2,r3,r4
U
T
D
..1.
まず，平面走査を行い，処理の対象となった MBR に対して処理を実行する．(b) の例では，
r1 と s2 が LRU バッファに読み込まれる．
..2 次に，前項で対象とした MBR に対して位数を求める．ここで MBR の位数とは，他の木の
MBR でまだ処理されていないものと交差する回数である．
.. 位数が大きい側の MBR を LRU バッファに固定 (pin) する．そして，その MBR と他の
3
MBR との交差を全て処理する．
.4. これが終了した後，通常の平面走査の順番で処理を続ける．
.
.
.
.
Ohsawa (Saitama Univ.)
GIS-7
11 / 21
最近接ペア検索
最近接ペア検索の例
最近接ペア検索 (CPQ: closest pair query)
ゴルフ場とテニスコートが近くにあるリゾートを探したい
.
..
.
dist(pi , qj ) ≥ dist(pz , ql ) ∀pi ∈ P ∧ ∀qj ∈ Q
Ohsawa (Saitama Univ.)
GIS-7
.
.
.
定義 1
.
..
2 つの点集合 P,Q が与えられ，それぞれの集合から取り出した 2 点 pz ,ql
のペア (pz , ql ), pz ∈ P, ql ∈ Q について次の式が成り立つ場合 (pz , ql ) を
1-CP と呼ぶ．
12 / 21
.
最近接ペア検索
２つの MBR 間の距離
2 つの R 木上のノード NP，NQ
それぞれの MBR：MP,MQ
/+0/#:&5+6
MP の４つの辺：r1,r2,r3,r4
/#:/#:&+56
MQ の４つの辺：s1,s2,s3,s4
/2
/3
MINDIST(ri,sj):辺 ri と sj 上の点の最小距離
/+0/+0&+56
MAXDIST(ri,sj):辺 ri と sj 上の点の最大距離
.
定義 2
..
2 つの MBR，MP と MQ に重なりが無いとき，
.
MINMINDIST (MP , MQ ) = mini,j {MINDIST (ri , sj )}
また 2 つの MBR に重なりがあるとき，
MINMINDIST (MP , MQ ) = 0
とする．また，２つの MBR が重なるときも，重ならないときも，次のように定義する．
MINMAXDIST (MP , MQ ) = min{MAXDIST (ri , sj )}
i,j
GIS-7
MAXMAXDIST (MP , MQ ) = max{MAXDIST (ri , sj )}
13 / 21
i,j
.
..
最近接ペア検索
.
.
.
Ohsawa (Saitama Univ.)
距離の不等式
2 つの MBR MP と MQ に含まれる２つの点 pi と qj において次の２つの
不等式が成り立つ．
不等式 1
MINMINDIST (MP , MQ ) ≤ dist(pi , qj ) ≤ MAXMAXDIST (MP .MQ ) (1)
不等式 2
dist(pi , qj ) ≤ MINMAXDIST (MP , MQ )
(2)
q
p
.
Ohsawa (Saitama Univ.)
GIS-7
14 / 21
.
最近接ペア検索
単純なアルゴリズム
CP1: CP の最短距離 T を ∞ とし，2 つの R 木の根ノードから探
索を開始する．
CP2: 全ての MBR のペアに対して，再帰的に探索を行う．
CP3: 2 つの R 木の葉ノードに達したとき，実際のオブジェクト
との距離 T1 を求め，T 1 < T であれば，T ⇐ T1 とする．
.
Ohsawa (Saitama Univ.)
GIS-7
15 / 21
最近接ペア検索
しらみつぶし法
CP1: CP の最短距離 T を ∞ とし，2 つの R 木の根ノードから探
索を開始する．
CP2: 内部ノードでは MBR のペアに対して MINMINDIST を計算
し，MINMINDIST ≤ T のときのみ下方に再帰的に検索を
行う．
CP3: 2 つの R 木の葉ノードに達したとき，実際のオブジェクト
との距離 T1 を求め，T 1 < T であれば，T ⇐ T1 とする．
CP2 により枝刈りが行える．
/+0/#:&5+6
/#:/#:&+56
/3
/2
/+0/+0&+56
.
Ohsawa (Saitama Univ.)
GIS-7
16 / 21
.
最近接ペア検索
単純な再帰的アルゴリズム
内部ノードにおいて，２つの MBR のペアに対して不等式 2(下記) の関係
を調べ，最小の MINMAXDIST の値が T より小さければ，直ちにその値
で T の値を更新することができる．
dist(pi , qj ) ≤ MINMAXDIST (MP , MQ )
(3)
CP1: CP の最短距離 T を ∞ とし，2 つの R 木の根ノードから探
索を開始する．
CP2: 内部ノードにおいて全ての MBR のペアに対して
MINMAXDIT を計算する．もしその最小値が T より小さけ
れば，その値で T の値を更新する．全ての MBR 同士のペ
アに対して MINMINDIST を計算する．MINMINDIST ≤ T
の関係を満たすペアのみについて下方探索を行う．
CP3: 2 つの R 木の葉ノードに達したとき，実際のオブジェクト
との距離 T1 を求め，T 1 < T であれば，T ⇐ T1 とする．
.
Ohsawa (Saitama Univ.)
GIS-7
17 / 21
最近接ペア検索
距離でソートする再帰的アルゴリズム
MINMINDIST が小さい MBR 同士は CP を含んでいる可能性が大きい．
そこで，中間ノードにおいて全ての MBR のペアに対して MINMINDIST
を計算し，それを昇順にソートする．そして，最小の MINMINDIST のペ
アから順に再帰的な呼び出しを行う．
CP1: CP の最短距離 T を ∞ とし，2 つの R 木の根ノードから探
索を開始する．
CP2: 内部ノードにおいて，全ての MBR のペアに対して
MINMAXDIST の最小値を計算する．もしこの値が T より
小さければ，その値で T を更新する．次に全ての MBR の
ペアに対して，MINMINDIST を計算し，それを昇順にソー
トする．このソートされた順番で，MINMINDIST ≤ T を
満たすペアのみについて再帰的に下方にたどる．
CP3: 2 つの R 木の葉ノードに達したとき，実際のオブジェクト
との距離 T1 を求め，T 1 < T であれば，T ⇐ T1 とする．
.
Ohsawa (Saitama Univ.)
GIS-7
18 / 21
.
最近接ペア検索
ヒープを用いた非再帰的なアルゴリズム
CP1: 2 つの R 木の根ノードから開始する．T の値を ∞ で初期化
する．またヒープを初期化する．
CP2: 内部ノードに対しては，全ての MBR のペアに対して
MINMAXDIST を計算する．もし，その値が T より小さけ
れば T をその値で更新する．次に全ての MBR のペアにつ
いて MINMINDIST を計算し，MINMINDIST ≤ T の条件を
満たすペアのみをヒープに投入する．
CP3: 葉ノードに達したとき，全ての点の組み合わせに対して距
離を計算し，その距離が T より小さければ，その値で T を
更新する．
CP4: ヒープが空になれば処理を終了する．
CP5: ヒープの先頭の要素を取り出す．もしそのペアの
MINMINDIST が T の値より大きければ処理を終了する．そ
れ以外のときこのペアに対して CP2 以下を繰り返す．
.
Ohsawa (Saitama Univ.)
GIS-7
19 / 21
最近接ペア検索
各種アルゴリズムの性能比較
EXH:しらみつぶし法
SIM:単純な再帰的アルゴリズム
STD:距離でソートする再帰的アルゴリズム
HEAP:ヒープを用いたアルゴリズム
図形の重なりが小さい時 (実行時間)
EXH > SIM > STD + HEAP
図形の重なりが大きい時（実行時間）
EXH + SIM > STD > HEAP
.
Ohsawa (Saitama Univ.)
GIS-7
20 / 21
.
最近接ペア検索
距離ジョイン
距離ジョイン
空間ジョイン：空間的位置関係として互いに重なりを持つ
距離ジョイン：２つのオブジェクトが一定の距離以内に入る
２つの集合 A,B から，予め定められた距離の範囲内に存在する要素を
１つづつ取り出す，要素ペアを求める演算：distance join
任意の川に最も近い街を求める
人口が１０万人以上で，川に最も近い街を求める
任意の川から 10km 以内の距離にある街を求める
集合 A の各オブジェクトに対して，集合 B 中での最近接オブジェクト
を探す演算：distance semi join
店と倉庫の集合が与えられたとき，各店に対して最も近い倉庫を求める
（店，倉庫）のペアについて，距離が近い順に出力される
各店に近い倉庫が探されるため，店は 1 回のみ現れるが，倉庫は複数回
現れる可能性がある（反射的でない）
.
.
Ohsawa (Saitama Univ.)
GIS-7
21 / 21
© Copyright 2024 ExpyDoc
