Spatial join

Spatial join

각 MBR이 겹치는 것을 찾아서 join을 하는 것임

위의 초록7개와 빨강 7개의 7*7 pair에 대해서 겹치는 것을 찾으면 됨

 

 

Join1

2개의 tree-depth가 같을 때, 사용가능함

위와 같은 logic을 따름

즉, 겹치는 E와 F가 leaf node이면 결과에 추가하고,

겹치는 E와 F가 internal node이면 다시 loop를 돌림

→ 단, 연산시간이 많이 걸림 (7*7=49 pair)

개선1. Restricting the search space (Join2) 

개선2. Spatial sorting and plane sweep

 

 

Join2: Restricting the search space

각 pair를 다 계산하는 것을 최적화시킴

→ root MBR (R, S)에서 겹치는 영역 내에서 존재하는 MBR에 대한 조합만 계산함

즉, 노란영역에 존재하는 초록3개 * 빨강2개의 조합(6개)만 고려하면 됨

추가로 노란영역과 겹치는 MBR을 scanning하기위해서

총 R의 7개, S의 7개를 검토해야하므로 

total 6+14=20의 비교만 하면 됨

위의 로직에서 JOIN1과의 차이는 IV(노란색)영역을 INPUT인자로 넣어주는 것임

 

 

 

 

Join3: Spatial sorting and plane sweep

1. lower-left코너의 x좌표를 기준으로 정렬함

2. Plane Sweep

[r1] -2번 비교

r1에서 시작하여 축을 오른쪽으로 이동하면서 s1과 겹치는 지 확인

(r1, s1)이 겹치므로, result-set에 append함

동일하게 (r1, s2)도 result-set에 append함

 

[r2] -1번 비교

r2와 s1은 x-range는 겹치지만 y-range가 겹치지 않으므로 제외

s2와는 x-range도, y-range도 겹치지 않으므로 제외 

 

[s1]s1은 r3와 겹치지 않으므로 제외

 

[s2] - 1번비교

s2는 r3와 겹치므로 result-set에 append함

 

따라서 총 비교횟수는 위와 같음

 

 

Spatial Hash Join

1. Hash join based on Space-driven structures (with redundancy)

2. Hash join based on Data-driven structures (with overlapping)

 

 

 

2. Hash join based on Data-driven structures (with overlapping) 상세 설명

A={1, 14, 10}

B={2, 4, 7, 11}

C={3, 8, 9}

D={5,6,12,13}

왼쪽 영역을 오른쪽 영역에 overlap 시키면

A'={c, d}

B'={a, b, d, g}

C'={e, g, h}

D'={a, e}

 

그러므로 아래와같이 대응되는 영역에서만 비교하면 됨

[A, A’], [B, B’], [C, C’], [D, D’] must be joined

위의 비교시 plan-sweep기법으로 비교하면 Hash join이 완성 됨

 

 

 

 

1. Hash join based on Space-driven structures (with redundancy)에 상세설명

 = Partition based Spatial Merge Join 라고도 함

R과 S에 대해 균일하게 분할 한다음 대응되는 영역만 비교하는 것임