R-tree를 활용한 다양한 질의 처리

Range query

 

 

index없이 모든 point들을 다 살펴보는것은 효율적이지 않음

반면, R-tree의 범위 질의를 통해 빠르게 query에 답할 수 있음

aggregation query:

특정 범위내에 있는 값에대해 집계처리(count, sum, avg, min, max)의 결과를 return하는 것

• Straightforward approach: reduce to a range query. 
• Better approach: along with each index entry, store aggregate of the sub-tree.

노란색 처럼 각 노드에 count 값을 미리 가지고 있음

Nearest Neighbor (NN) Query

eg) Given a query location q, find the nearest object

 

이 때 R-tree를 활용하면 가장 가까운 지점에 있는

MBR까지의 거리를 반지름으로 하는 원을 그려(원을포함하는 MBR)

그 안에 있는 점들만 탐색하는 방법을 사용함

 

MBR face property

MBR이란 각 한 변은 적어도 하나의 포인트를 접해서 만들어지는 것임

→ 이걸 MBR face property라고 함

Search improvement

MINDIST and MINMAXDIST를 사용하여 search 성능을 높일 수 있음

MINDIST

• MINDIST(p,R) is the minimum distance between p and R 

  with corner points l and u

 

설명: 모든 임의의 object ‘o’은 P와 R사이의 거리보다 항상 크거나 같다.

MINMAXDIST

파란점에서 가장 가까운 수직변에서 가장 먼 것은 A임 = minmaxdist

가장 가까운 수평면에서 가장 먼것은 B이므로 그 두개의 점이 선택이되고

그중에서 거리가 짧은 값을 반지름으로 했을 때, 그 원안에 들어오는 점에 대해 search를 하면 됨

 

** MINMAXDIST를 반지름으로 하는 원을 그렸을 때, 

   그 원안에는 적어도 1개의 점이 있다는 것을 의미함 

아래 그림에서 진한점선을 반지름으로 하는 원안에 들어오는 point만 search 하면 됨

 

 

point O는 초록점과 NN에 속하는 점이 될수 없다는 것을 뜻하는 그림임

 

예제 3번도 참고하기

** DFS: Depth first search

** BFS: Breadth first search

NN search: Best-First

: DFS와 BFS를 다 고려하여 그중에 가장 best인 것을 선택하는 것임

priority queue : 정렬된 하나의 배열이라고 생각하면 됨

배열의 첫번째에 가장 작은 값이 오는 것을 min hip, 

배열의  첫번째에 가장 큰값이 오는 것을 max hip이라 함

best-first의 예시

 

여러번 반복해서 h가 q의 nn이라고 할 수 있음

 

실제 object이 return되면(i) loof 종료

관련 pseudo 코드는 아래와 같음

NN Full-Blown Algorithm

Minmaxdist를 사용하여 search해야할 범위(delta)를 계속 줄여나가는 방법

밑줄친 노란색은 적어도 (q,se) 범위 내에 NN에 해당하는 점이 1개는 존재한다는 것

iteration을 돌면서 search하는 범위(delta)를 계속 줄여 나감

Action(delta)		Heap
visit root	inf.	E1	…
E1	17	E2	skip	E3	13	E5	13	E4	10

각 노드가 insert 될 때마다 delta가 (E1)17→ (E3)13 → (E4)10로 업데이트 됨

Close Pair Query

점 2개를 묶어 둘사이의 거리가 alpha보다 작은 것들 찾는 것

 

여기서 alpha보다 거리가 작은 것은 r1, r2, r3밖에 없음

 

단순히, 모든 pair들의 거리를 다 계산하는 것보다 R-tree를 사용하면 더 효율 적으로 계산할 수 있음

 

필기한거 가져오기