SDBMS ④ The Linear Quadtree

 

SDBMS 공간데이터베이스

 

④ The Linear Quadtree

 

 

---

 

 

0. The Quadtree

 

 

공간을 사분할하여 데이터를 저장하는 구조

단순하게 NW, NE, SW, SE로 사분할하여

공간 상에서의 quadrant ↔ 트리의 leaf node ↔ page 로 대응,

quadrant와 겹치는 데이터의 [mbr,oid]를 해당 page에 저장한다.

 

아주 직관적이고 구현이 쉽다. 그러나  

 

 

- node 당 child의 수가 4개로 고정되어있다. 빈 quadrant에 대응되는 node도 생겨 page waste 발생

- quadrant가 작을수록 겹치는 게 많아 중복저장이 증가한다. (grid file에서와 같음.)

- 한쪽으로 데이터가 집중될 경우 leaf node의 깊이가 각각 달라진다.
  따라서 (B+tree와 다르게) 쿼리 수행이나 데이터 입력 시 최대 시간을 보장할 수 없다.

- disk page와 quadtree의 mapping자체가 어렵다. Node의 fanout이 작기 때문

 

이를 보완하고자

space filling curve를 이용해 page waste를 줄이고 depth를 일정하게 만든 게 linear quadtree이다.

 

 

---

 

 

 

1. Space Filling Curves

 

대개 total order가 성립하지 않는 공간에서, space filling curve는 total order을 강제(?)한다.

 

Z-order curve(위), hilbert curve(아래)

 

가장 흔한. Z-order curve(Morton curve)와 Hilbert curve(그리고 갑자기 떠오른 문제)

 

이외에도 여러 종류의 curve가 있다. 3차원 버전도 검색하면 많이 나온다. 위키에도 잘 나와있고

 

Space filling curve는 공간에 사전식 순서를 만족하는 값을 준다.

(lexicographical ordered label을 매겨 total order를 만족하게 한다.)

 

위 그림에서는 각 공간의 라벨 값을 써놓은 거고,,

라벨은 이렇게 공간을 나눈 횟수만큼을 자릿수로 하는 수열로 나타낸다.

 

 

 

 

공간에 억지로(?) 부여한 total order가 효율적이기만 하진 않다.

 

 

Z-order 곡선은 한 quadrant 내에서 NW→NE→SW→SE 순으로 우선순위를 매긴다.

SW→NW→SE→NE 순으로 매기기도 하는데, 뭐가 됐든 여기서의 핵심은 Z모양으로 매긴다는 거다.

따라서 실제로는 두 공간이 멀지만 가까운 것처럼 보이는 경우(31,32)와

실제로 두 공간이 가깝지만 먼 것처럼 보이는 경우(47,58)가 모두 생길 수 있다.

 

힐베르트 곡선은 라벨 값의 차가 1인 두 공간은 반드시 서로 이웃하기 때문에

멀지만 가까운 것처럼 보이는 경우는 존재하지 않지만

여전히 가깝지만 먼 것처럼 보이는 경우(11,53)가 존재한다.

 

 

---

 

 

2. The Linear Quadtree

 

Linear quadtree는 quadtree의 leaf node의 label을 key로 하는 B+tree 구조이다.

아래는 Z-order를 이용한 구조

 

 

Quadrant에 대응되는 entry를 통해 page에 접근할 수 있다는 점은 동일하다.

 

Linear quadtree는 B+tree를 이용하기 때문에

entry는 label의 사전 순으로 배열되며 모든 leaf node의 깊이가 동일하다.

Quadrant 01이 또 사분할 되는 경우

quadtree에서는 01에 해당하는 node가 4개의 child를 갖게 되지만

linear quadtree에서는 01을 삭제하고 010, 011, 012, 013을 삽입한다.

 

 

---

 

 

3. Query

 

Linear quadtree는 아무튼 최종 구조는 B+tree와 같기 때문에

query수행 시 z-order를 따라 quadrant를 탐색하게 된다.

 

Point Query: 주어진 점을 포함한 객체 검색

Window Query: 주어진 사각형 범위와 겹치는 객체 검색

 

 

1. Point Query, P(a,b)

begin
	result = {}
	
	l=PointLabel(a,b)		// Compute label of point
	L=MaxInf(l)				// Get the entry of label L
	page=ReadPage(L.p)	// Get the page of the entry
	for each e in page do
		if(P is in e.mbb) then reault+=(e.oid)
	end for

	return result
end

Linear Quadtree에서는 점 P가 존재하는 quadrant의 크기가 정확히 정해지지 않는다.

따라서 MaxInf함수로 정확한 entry를 찾는다.

 

 

 

그림에서 가장 작은 quadrant는 전체 공간을 64분할한 크기이므로 여기서 PointLabel은 세 자리 수열의 라벨을 구한다.

MaxInf는 linear quadtree에서 라벨 값을 비교해 entry를 찾는다.

 

점 P의 경우 세 자리 라벨은 320이므로 사전 순으로 32와 33 사이에 존재해야 하고, 따라서 라벨이 32인 entry가 L이 된다.

점 R의 경우 023 그대로 찾으니까, MaxInf는 라벨의 lower bound 값을 라벨로 하는 entry를 찾는다고 보면 될 듯.

 

 

2. Window Query, W(x1, y1, x2, y2)

begin
	result = {}
	
	l1=PointLabel(x1,y1)		// Compute label of NW, SE point
	l2=PointLabel(x2,y2)

	L1=MaxInf(l1)
	L2=MaxInf(l2)
	Q=Range([L1,L2])			// Get the entries of label L1~L2

	for each q in Q do
		if(W INTERSECT Quadrant(q)) then
			page=ReadPage(q.p)
			for each e in page do
				if(P is in e.mbb) then reault+=(e.oid)
			end for
		end if
	end for

	Sort(result), RemoveDupl(result)
	return result
end

Window query의 경우 해당 사각형(W)이 존재할 수 있는 quadrant의 최소, 최대 라벨을 구해(line 4-5) 그 범위 내의 entry를 모두 확인한다.(line 7-11) 다만 실제로 entry에 겹치는 quadrant만 탐색한다.(line 12)

 

(당연하지만) 여기선 (x1,y1)이 NW, (x2,y2)가 SE라고 생각하자. Z-order가 NW-NE-SW-SE 순이니까

 

 

 

위에서 Q={01,020,021,022,023,03,10,11,12}

그러나 실제로 탐색할 entry q는 01, 03, 10, 12뿐이다.

 

 

* 시간복잡도

시간복잡도라기 보단 IO count라고 봐야하나

트리의 깊이를 d라 할 때

포인트 쿼리는 d+1 (MaxInf+ReadPage)

윈도우 쿼리는 3d+k (MaxInf*2+Range+ReadPage)

MaxInf랑 Range모두 entry까지 도달하려면 d만큼 내려가야하니까

 

 

---

그림: Spatial Databases: With Application to GIS, Philippe Rigaux

 

 

 

계속 space-driven 이랑 data-driven 구조를 정리할 예정

Space-driven은 Z-Ordering tee랑 KD tree 두 개 남았고

Data-driven으로 넘어가면서 R tree랑, 되면 M tree도 정리할 듯.

 

SAM설명 끝나면 KNN 다루고, RNN, CNN, Spatial Keyword까지 좀 정리하려는데

뒷부분은 사실 크게 다룬 게 없어서 찾아서 공부를 좀 해봐야할지

R tree쪽 볼 때는 다시 구현했던 코드도 좀 손볼까 하는데 될지

솔직히 지금 이거 정리할 떄가 맞는지도 모르겠다