공간 데이터 베이스 - Road Network
Road Network
1. 개요
이전까지 공간 데이터 베이스에 관련된 포스팅은 직선거리에 대한 내용이었다.
하지만 실제 우리가 거리와 공간에 대해서 질의할 때 얻는 답변은 실제로 우리가 가고자하는 곳에 어떤 도로나 길을 타고 갔을 때 얼마나 가야 가장 가깝게 도착할 수 있는지 등에 대한 내용이다.
2. Graph Modeling of Road Network
길에 대해서 탐색하기에 앞서, 어떤 곳으로 가는데 길 정보가 필요하기 때문에 이를 위해서는 별도로 도로를 모델링해서 탐색 정보에 포함해야한다.
이를 Road Network라고 한다. 아래의 그림을 보자.
이렇게 생긴 지도가 있다고 해보자. 각 원은 어떤 건물이나 목적지가 될 수 있고 선은 실제 도로를 그린거라고 해보자. 하지만 이대로 쓰기는 어렵다. 좀 더 계산하기 편하게 아래와 같이 모델링 할 수 있다.
직선만으로 표현하면 거리를 재는데 용이해진다. 따라서 꺾이는 부분에는 빨간점으로 임의의 node를 선정해서 모델링했다.
위와 같이 모델링하면 사용하기 편하다. 아래는 어떻게 Road Network를 그래프로 모델링하는지에 대한 내용이다.
엣지에 저장된 거리: 그래프의 단일 엣지는 실제 도로 구간 하나를 나타내고, 그 엣지의 weight로 길이(혹은 주행 시간)를 기록한다.
예: 교차로 A–B를 잇는 도로 길이가 120 m이면 그 엣지의 $d_{N}(A,B)=120$ (또는 시간 기준 가중치).비직접 연결 노드의 거리 = 최단 경로 길이: 노드 A와 C가 직접 연결되어 있지 않다면 A→C 거리는 A→…→C 로 연결된 경로들 중 가장 짧은(또는 최소 비용) 경로 길이다. 즉 그래프 최단경로 개념(다익스트라 등)인 셈이다.
비대칭성 예시: 일방통행 도로가 있으면 A→B로 갈 수 있지만 B→A는 다른 길(우회)로 가야 하므로 거리/시간이 달라진다.
예를 들어 A→B는 100 m, 하지만 B→A는 일방통행이라 우회해 600 m라면 $d_{N}(A,B)=100\ne d_{N}(B,A)=600$ 으로 환산한다.유클리드 하한 성질(직선거리는 항상 더 작거나 같다): 실제 도로로 이동하는 거리는 직선보다 같거나 길다(도로가 직선으로 이어지지 않거나 우회가 있기 때문). 따라서 직선거리로부터 네트워크 거리의 하한을 얻을 수 있다. 이 성질이 후보 필터링(예: RER, IER)에서 핵심으로 사용된다 — “직선 거리가 반경 e를 넘으면 실제 도로로는 그보다 더 멀 것이다” 라는 안전한 배제 규칙을 만들 수 있다.
3. Nearest Neighbor Queries in Spatial Network DB
1) IER(Incremental Euclidean Restrictions)
a. 알고리즘
어떤 점 q 로부터 Road Network 상에서 가장 가까운 노드를 찾고 싶을 때이다.
유클리드 거리는 항상 네트워크 경로 거리의 하한이므로 유클리드 거리가 현재 최단 네트워크 거리보다 크거나 같으면 그 후보 및 그 뒤 후보들은 더 가깝지 않다.
- 모든 노드를 쿼리점 q로부터 유클리드 거리 순으로 정렬하거나(혹은 유클리드 NN을 반복 추출할 수 있는 구조 사용).
- 첫 번째(가장 직선으로 가까운) 후보 c1 을 꺼내 실제 네트워크 최단경로 거리 dN(q, c1) 를 계산한다. 이 값을 현재 최선 bestDist 로 설정하고, 최선 노드 bestNode = c1. 3.다음 후보 ck 를 꺼낸다.
- 만약 euclidDist(q, ck) >= bestDist 이면 탐색 종료(왜냐하면 네트워크 거리 dN(q, ck) ≥ euclidDist(q, ck) 이므로 ck는 더 작을 수 없음).
- 그렇지 않으면 d = dN(q, ck) (실제 네트워크 거리)를 계산한다.
- 만약 d < bestDist 이면 bestDist = d, bestNode = ck.
- 아니면 다음 후보로 계속.
- 후보가 없거나 위의 종료 조건에 걸리면 bestNode 반환한다
b.장점/단점
- 유클리드 거리로 후보를 잘 걸러낼 수 있으면 효율적(짧은 후보 목록만 네트워크 거리 계산)이다.
- 그러나 유클리드-네트워크 순서가 매우 불일치하면(유클리드 가까움이 네트워크에서 멀 수 있음) 많은 후보를 검사해야 한다.
c. K-NN 확장
위 과정을 k개 답을 찾을 때까지 반복하고, $d_{N}max$는 k번째로 큰(가장 먼) 네트워크 거리로 갱신하여 추가 후보를 배제한다
2) INE(Incremental Network Expansion)
a. 알고리즘
- IER이 유클리드 순으로 후보를 뽑는 방식이라면, INE는 네트워크 그래프 자체를 확장(탐색) 하면서 최근접을 찾는다.
- 시작 노드에서 우선순위 큐(거리 기준)로 인접 노드를 순차적으로 확장해 나가며, 방문하는 도중 발견한 객체를 후보 집합에 추가.
- 네트워크 탐색이 $d_{N}max$(현재 발견된 최댓값)보다 더 먼 거리를 가리키면 멈추는 방식(큐에서 꺼낸 거리가 $d_{N}max$보다 크면 중지).
b. 장점/단점
- 유클리드 근사에 의존하지 않으므로 유클리드-네트워크가 크게 어긋나는 상황에서 우수.
- 그러나 네트워크 전체를 많이 탐색해야 할 수 있어 비용이 클 수 있음(특히 고밀도 네트워크에서).
4. Range Queries in SNDB
1) RER(Range Euclidean Restriction)
a. 알고리즘
- R-tree 등 공간 인덱스로부터 유클리드 반경 e 안에 들어오는 모든 객체 집합 C 을 찾는다.
(쿼리: center = q, radius = e — Euclidean range query) - 결과 집합 𝑅 ← ∅
- 각 후보 𝑜 ∈ 𝐶 에 대해 실제 네트워크 최단거리 𝑑(𝑞,𝑜)를 계산한다(예: 도로 그래프에서 Dijkstra).
- 만약 𝑑(𝑞,𝑜)≤𝑒 라면 𝑅 ← 𝑅∪{𝑜}
- 모든 후보를 검사한 뒤 𝑅 을 반환한다.
2) RNE(Range Network Expansion)
a. 알고리즘
- 쿼리점 q와 네트워크 반경 e가 주어진다.
- 네트워크 탐색을 통해 거리 e 이내에 닿는 모든 세그먼트들을 찾아 집합 QS로 만든다. (이 단계가 “Range Network Expansion”의 핵심: 어떤 간선들이 범위에 포함되는지 판단)
- 이제 QS에 포함된 세그먼트들 위에 있는 실제 데이터 객체들을 object R-tree를 이용해 검색한다:
- R-tree의 각 노드 엔트리에 대해, 그 엔트리의 MBR이 QS의 어떤 세그먼트들과 연관되는지(교차하는지)를 계산해서(QS_i), QS_i가 비어 있지 않으면 그 자식 노드만 재귀적으로 탐색한다.
- 리프 노드에서는 plane-sweep이나 유사한 방식으로 리프 내부 엔트리(객체 MBR)와 QS_i를 검사하여 실제 객체를 수집한다.
- 중복된 객체가 있을 수 있으므로 정렬/중복 제거 후 최종 결과를 반환한다.
5. Closet-Pairs Euclidean Restriction
1) 알고리즘
입력: S(R-tree), T(R-tree), k(개수) 출력: 네트워크 거리 기준으로 가까운 k 쌍
- 먼저 유클리드 기준으로 가장 가까운 k개 쌍을 구한다(즉 평면에서의 k-nearest pairs).
- 각 초기 k쌍에 대해 네트워크 거리(도로상의 최단경로 거리)를 계산한다.
- 네트워크 거리 기준으로 오름차순 정렬(가장 작은 거리부터).
- 현재 top-k 중 가장 큰(=k번째) 네트워크 거리를 dEmax 로 설정(이 값이 갱신 임계값).
- 아래 내용을 반복한다.
- 다음으로 유클리드 기준에서 가까운 쌍을 하나 더 가져온다(스트리밍 방식으로 다음 유클리드 쌍을 반환).
- 이 쌍의 네트워크 거리를 계산.
- 새로 들어온 쌍이 현재 k번째보다 더 작으면(top-k 갱신 가능) 집어넣고 dEmax 재설정(항상 k번째의 네트워크 거리를 반영).
- 종료조건: 다음으로 반환되는 유클리드 거리(d_E(s’,t’))가 현재 dEmax 보다 커지면 더 이상 네트워크 거리로 top-k를 교체할 수 없다. 따라서 반복을 종료한다.
※ 추가 업데이트 및 검증 예정이다.
참고자료
- Shashi Shekhar and Sanjay Chawla, Spatial Databases: A Tour, Prentice Hall, 2003
- P. RIigaux, M. Scholl, and A. Voisard, SPATIAL DATABASES With Application to GIS, Morgan Kaufmann Publishers, 2002