Road Network Query Processing

Road Network layer는 graph로 표현됨

* 휘어진 도로는 구간을 짧게 쪼개 직선거리로 표현함

아래 회색점이 곡선 구간을 작게 쪼갠점임

 

네트워크상의 두 노드의 거리 표현 방법

직접 연결 안된 두 노드의 거리는 두 노드의 최단거리로 표현한다는 의미임

 

 

 

네트워크 distance의 속성1

 

네트워크 distance의 속성2

네트워크 distance는 Euclidean distance보다 항상 크거나 같다.

Euclidean distance: 최단 직선거리임

 

 

실제 도로와 그것을 네트워크 modeling으로 표현한 것

b는 각각의 노드로 갈수 있는 방향을 표현함

 

 

 

 

Nearest Neighbor Queries in Network DB

1. IER(Incremental Euclidean Restrictions) Algorithm

    : 회색영역을 점점 줄여나감 (k=1 일 때, 시험!)

(1st)에서 유클리디언 distance기준으로 가까운 점은 PE1임

- 작은 원은 PE1까지의 직선거리를 반지름으로 하는 원

* 작은원 내에 직선거리로 q에 가장 가까운 점은 PE1한개임

- 큰 원은 PE1까지의 실제 도로상거리를 반지름(dEmax)으로 하는 원

* 두 원의차이(회색 음영표시)는 직선거리로는 PE1보다 멀리있으나,

   실제 도로상 거리로는 PE1보다 가까이 있을 수 있는 영역

   (PE2가 존재하는 영역. PE2는 Network distance기준 q와 제일 가까움)

 

(2nd)에서는 PE2를 가지고 PE1과 같은 작업을 한 것

 

결과1)

1st에서의 dEmax = dN(q, PE1)보다 

2nd에서의 dEmax = dN(q, PE2) 가 더 작으므로

PE2가 q에 더 가까운 호텔이라 할 수 있음

결과2)

하지만 여전히 2nd에서도 회색 음영이 존재하므로

PE2가 q에 가장 가까운 호텔이라 할 수 없음 

→ 그러므로, 다른점 PE3를 검토

결과3)

PE3와 q의 직선거리는 dEmax = dN(q, PE2)보다 크므로

PE3는 가까운 호텔이라고할 수 없음

최종 결과)

PE2가 실제 거리상 q와 가장 가깝다고 할 수 있음

(단, 여전히 회색 음역이 존재함)

 

 

IER 알고리즘 코드

11번은 위에서의 결과3의 설명과 같은 상황임

 

 

 

2. INE(Incremental Network Expansion) Algorithm (k=1일 때 시험)

위의 그림에서 가장 가까운 직선거리는 p1이나, 

실제 거리가 너무 멀게 되면 IER기법은 시간이 오래걸린다는 단점이 있음

해결책: INE

위와 같이 network상에서 가장 가까운 노드를 먼저 파악하는 것으로 시작함

n1, n2를 선택하고 Q = <(n1,3), (n2,5)> 둘 중 가까운 n1을 선택함

n1과 가까운노드는 n7이고 n1근처에 호텔이 없으므로 n1은 제거

Q = <(n2,5),(n7,12)> 에서 가까운 n2노드를 선택

n2와 가까운 노드인 n4를 확인하여 그 근처에 호텔이 있는지 파악함( 여기 다시 듣기: 50분뒤 설명 확인)

P5호텔을 발견 그러므로 dNmax를 ,dNmax = dN(q, p5) = 7로 업데이트함

그 다음 Q = <(n4,8),(n3,9),(n7,12)>와 같이 업데이트 해줌

근데 여기서 가장 작은 (n4,8)값이 이미, dNmax보다 크기 때문에 종료함