On k-Path Covers and their Applications

On k-Path Covers and their Applications, Stefan Funke, Andre Nusser, Sabine Storandt

 

1. 대규모 도로 네트워크에서, 길이가 k인 모든 경로에 대해 최소 하나 이상의 노드를 포함하는 작은 노드 집합 (k-Path Cover)를 구성하는 문제를 다룬다.

2. 위 k-Path Cover를 실제 대규모 그래프에서 매우 작게 효율적으로 구축할 수 있는 Pruning 알고리즘을 제시하며, 이는 기존 k-Shortest-Path Cover 방법보다 더 나은 결과를 얻는다.

3. 구성된 k-Path Cover는 오버레이 그래프의 기반이 되어, 사용자별 선호도를 반영하는 개인화된 경로 계획 질의를 기존 Dijkstra 알고리즘보다 훨씬 빠르게 처리 가능하다.

 

 

k-Path Cover

주어진 그래프에서 길이가 k인 모든 경로가 특정 노드 집합 C에 의해 커버되도록 하는 최소 크기의 노드 집합 C를 찾는 문제입니다. 여기서 '커버된다'는 것은 경로 상에 C에 속하는 노드가 적어도 하나 존재한다는 의미입니다. 이 논문에서는 특히 도로 네트워크와 같이 매우 큰 그래프에서 효율적으로 작은 k-Path Cover를 구성하는 알고리즘을 제시하고, 그 응용 가능성을 탐구합니다.

Spatial Network Databases (SNDB)

도로 네트워크와 같은 공간 네트워크 상에 위치한 지리적 개체들을 관리하고, 네트워크의 연결 속성을 고려한 효율적인 데이터 검색을 지원하는 데이터베이스입니다. Google Maps, Bing Maps, Yahoo Maps 등이 SNDB의 대표적인 예시입니다. 이 논문에서는 SNDB에서 대용량 데이터를 처리하고 경로 관련 질의를 효율적으로 처리하기 위해 k-Path Cover를 활용하는 방법을 제시합니다.

k-Shortest-Path Cover

가중치가 부여된 그래프에서 길이가 k인 모든 최단 경로가 특정 노드 집합 C에 의해 커버되도록 하는 최소 크기의 노드 집합 C를 찾는 문제입니다. k-Path Cover와 유사하지만, 모든 경로가 아닌 최단 경로만을 고려한다는 점에서 차이가 있습니다. 이 논문에서는 k-Shortest-Path Cover를 구성하는 알고리즘을 개발하고, k-Path Cover와의 비교 분석을 통해 각 방법의 장단점을 파악합니다.

VC-Dimension

집합 시스템의 복잡도를 측정하는 척도입니다. VC-Dimension이 d라는 것은, 해당 집합 시스템에서 크기가 d인 임의의 부분집합을 '산산조각'낼 수 있다는 의미입니다. 여기서 '산산조각낸다'는 것은 부분집합의 모든 가능한 부분집합을 해당 집합 시스템의 원소와의 교집합으로 표현할 수 있다는 뜻입니다. 이 논문에서는 최단 경로 시스템의 VC-Dimension을 분석하여 k-Shortest-Path Cover 문제에 대한 근사 알고리즘을 설계하는 데 활용합니다.

Personalized Route Planning

개인의 선호도나 운전 스타일과 같은 개인화된 요소를 고려하여 최적의 경로를 찾는 문제입니다. 전통적인 경로 탐색 알고리즘은 고정된 기준(예: 최단 거리, 최소 시간)만을 고려하지만, Personalized Route Planning은 사용자의 다양한 요구사항을 반영하여 더욱 만족스러운 경로를 제공하는 것을 목표로 합니다. 이 논문에서는 k-Path Cover를 활용하여 Personalized Route Planning 질의를 효율적으로 처리하는 새로운 프레임워크를 제시합니다.

 

초록

본 논문에서는 수백만 개의 노드와 엣지를 가진 도로 네트워크 환경에서, 작은 k-Path Cover를 구성하는 문제를 다룬다. 

매우 작은 k-Path Cover를 생성하기 위한 효율적인 알고리즘을 제공하는 것이 목표이다.

 

서론

회사들이 지리 공간 데이터를 대규모로 획득하면서, SNDB에서 처리할 데이터 양이 증가했다. 

작은 k-Path Cover로부터 이점을 얻을 수 있는 SNDB에 대한 몇 가지 응용 프로그램을 살펴보자.

1. 여행 경로

일부 경로는 이미 결정한 상태이고, 그 경로를 따를 건데 '주유' 혹은 '쇼핑' 기회에 관심이 있다고 해보자.

그럼 이럴 때 보통 생각 방법은, 이미 결정된 일부 경로 pie에 대해, pie의 모든 노드로 데이터 구조 D를 쿼리해볼 수 있는 것이다.

근데 pie가 엄청나게 크면.. 계산량이 너무 많아질 것이다. 따라서 이에 대한 대안으로 생각해낸 것이 k-Path Cover이다.

k-Path Cover를 식별하고, 그 C에 대해서만 D를 구성하는 것이다. 

 

2. 경치 시각화

만약 하이킹 경로를 제안하는 프로그램이 있다고 생각을 해보자. 

이때 화면을 조금 축소하려 한다. 그럼 기존 경로의 모든 단일 노드를 인터넷을 통해 전송하는 것은 대역폭 낭비가 될 것이다.

그래서 생각한 것은, 각 경로에서 k번째 노드마다의 경로만을 보여주는 것이다. 

근데 이렇게 하면 약간의 한계가 있는 것이, 경로가 겹치는 경우이다.

A경로와 B경로가 겹쳐진다고 할 때, 그럼 그 겹치는 부분은 같은 노드로 샘플링되는 것이 일관성있고 보기에 좋을 것이다.

그래서 단순히 매 k번째 노드를 선택하는 대신, k-Path Cover C에 속하는 노드들만을 선택하여 경로를 간략화하는 방식을 택한다.

 

3. 운전 스타일 개인화

사람마다 운전 속도가 다양하고, 가스 가격 vs 이동 시간 등에 대한 가중치가 사람마다 다를 것이다. 

따라서 출발지/목적지 뿐만 아니라 도로 네트워크에서의 최적 경로를 계산하는 방식이 개인화될 수 있을 것이다.

 

오버레이 그래프는, 복잡한 기본 지도 위에 주요 지점(랜드마크 혹은 주요 도로망)을 간략히 표시한 또다른 지도를 덧씌우는 것이다.

원본 그래프는 너무 커서 경로를 찾는 데 시간이 오래 걸린다면, 오버레이 그래프는 훨씬 가볍다.

 

위 이유로 원래 그래프보다 훨씬 빠르게 오버레이 그래프에서 검색하여 최적의 경로를 찾을 수 있다.

 

결론적으로, 모든 적용에서 k-Path Cover를 포함하는 것이 중요하다는 것을 강조한다.

 

 

관련 연구

k-Shortest-Path Cover 문제에서, 고정된 메트릭에 대한 경로 쿼리의 속도를 높일 수는 있었지만,

최신 기술에 비해 쿼리 속도가 떨어지고, 고정된 엣지 가중치에 의존하기에 사용자가 달라지며 엣지 가중치가 달라지는 경우 전처리를 다시 수행해야 하기에 동적인 요구에 적합하지 않은 문제가 있었다.

 

Customizable Route Planning을 위해 제안된 3단계 접근법도 있었다. 

1. 메트릭 독립적 전처리 2. 메트릭에 따른 사용자 정의 3. 쿼리 처리 의 단계로 진행됐는데, 

메트릭이 바뀔 때마다 2단계를 다시 수행해야 되어 느리다는 단점이 있다.

따라서 동적인 쿼리를 위해 2-3단계를 병합하고 메트릭 독립적 전처리는 유지하면서 메트릭 변경을 쿼리 시간에 직접 처리하는 방식을 제안한다.

 

위의 방안으로, 각 엣지가 d개의 관련 비용 c1(e), c2(e), ..., cd(e)를 가질 때, 쿼리 시 가중합 비용 c(e) = a1c1(e) + a2c2(e) + ... + adcd(e) 기준의 최단 경로를 효율적으로 계산하는 기법도 제안했다. 

하지만 이때는 d=2, 3인 경우를 제외하고는 speed-up 효과가 크게 감소했으며, 서로 다른 성격 메트릭에는 성능이 저하됐다.

 

본 논문의 주요 기여

작은 k-Path Cover를 계산하는 효율적인 알고리즘을 고안한다.

k-Shortest-Path Cover에 대한 이론적인 근사 보장이 가능하다.

위 사실은 epsilon-net theory를 사용하여, 그래프의 최단 경로 시스템인 VC-dimension 속성에 기반하여 효율적인 알고리즘 설계가 가능하다.

 

2. 형식적 정의

입력은 단순 방향 그래프 G(V, E)로, 경로 pie는 통과하는 정점 목록으로 표현할 수 있고,

정점이 중복되지 않는 단순 방향 그래프이기에 정점이 두 번 이상 나타나지 않는다.

 

3. 이론적 분석

VC 차원이란, 모델 또는 함수 집합의 '학습 능력'이나 '표현력'의 복잡성을 측정하는 지표이다. 

Shatter : U'에 속한 원소들만으로 만들 수 있는 모든 종류의 부분집합들을, S의 원소들과 U'의 교집합을 통해 구현할 수 있는 능력.

최종적으로 VC 차원은, 집합 시스템 (U, S)에서 S에 의해 shatter 될 수 있는 U의 가장 큰 부분집합 U'의 크기이다.

이 논문에서 VC 차원은, 그래프의 경로 집합 S가 정점 집합 V의 부분 집합 U'를 얼마나 다양하게 shatter할 수 있는가를 말한다.

 

이전 연구에서 VC 차원이 최대 2라고 주장했는데, 이것이 directed(방향) graph에서는 성립하지 않는다는 것을 증명해낸다.

물론 그래프 내의 모든 정점 쌍에 대해, s에서 t로 가는 '유일한 최단 경로'가 존재한다는 조건을 가진 채로 말이다.

이런 그래프가 있을 때, 정점 집합은 {a, b, c}이고, 각 부분집합은 공집합, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} 이다.

shortest path는 π(a, a)={a}, π(b, b)={b}, π(c, c)={c}, π(a, b)={a, b}, π(b, c)={b, c}, π(c, a)={c, a}, π(a, c)={a, b, c}이다.

이때 노드 집합 {a, b, c}가 shatter될 수 있는가를 확인해보려면, {a, b, c}의 모든 부분집합이 그래프의 어떤 최단 경로 π와의 교집합으로 표현될 수 있는가를 확인하면 된다.

이때 최단 경로들은 아래와 같이 교집합으로 표현될 수 있다.

{a, b, c} ∩ π(a, a) = {a}
{a, b, c} ∩ π(b, b) = {b}
{a, b, c} ∩ π(c, c) = {c}
{a, b, c} ∩ π(a, b) = {a, b}
{a, b, c} ∩ π(b, c) = {b, c}
{a, b, c} ∩ π(c, a) = {a, c}

{a, b, c} ∩ π(a, c) = {a, b, c}

따라서 노드 집합 {a, b, c}는 shatter될 수 있다.

 

하지만, 같은 방식으로 진행했을 때, 만약 v1->v2->v3->v4->v1로 진행되는 directed graph라고 하면, 

{v2, v4}를 전체집합과 경로와의 교집합으로 표현할 수 없기에, 네 개의 정점이 산산조각 될 수 없음을 보여줌으로써 VC-dim의 상한은 3이 된다.

 

4. k-Path 구성

4-1. 가지치기 알고리즘

노드 v를 C에서 가지치기 할 수 있을까 여부를 결정하기 위해서는, 현재 C의 다른 노드를 포함하지 않는 v를 통해 k-node 경로가 없는지 확인해야 한다. 즉, C의 다른 노드에 도달할 때까지 v의 모든 나가거나 들어오는 경로를 탐색해야 한다. v에서 시작하여 C의 다른 노드를 포함하지 않는 모든 outgoing path와, v에서 시작하여 C의 다른 노드를 포함하지 않는 모든 incoming path를 탐색한다. 이때 가장 긴 path들을 탐색하여, 두 경로의 합이 길이 k경로가 되는지 확인하는 방식이다. 이런 들어오고 나가는 경로 조합이 길이 k의 연결된 경로를 생성한다면,  v를 C에 유지해야 한다.

 

쉽게 말해 v를 C에 유지해야 하는 조건은, v를 통과하는 k개 노드로 구성된 어떤 경로에서, 이 경로 상에는 v외에 현재 커버 집합 C에 속한 다른 노드가 하나도 없는 경우 이다. 

 

pruing 알고리즘 접근 방식의 속도적 이점이 있는 이유는,

naive 알고리즘은 각 정점에서 시작하는 모든 k개 노드 경로를 열거하고 정리하기에 공간 소모가 막대하여 실용적이지 않다.

pruning 접근 방식은 커버 집합 C를 전체 정접 집합 V로 초기화하여 필요하지 않은 노드를 하나씩 제거한다. 초기 단계에서는 커버 집합 C가 거의 전체 정점 집합과 같기 때문에, 탐색은 거의 즉시 다른 노드에 도달하게 된다. 탐색 범위가 제한적이기 때문에 훨씬 빠르다. 

 

또한 가지치기 알고리즘이 실행되는 동안, 어떤 단계를 거치든 현재까지 선택된 정점들의 집합 C가 항상 k-APC 정의를 만족한다.

이 알고리즘으로 최종에 남은 노드들은 각 커버 집합에 존재해야 하는 정당한 이유가 존재하게 된다. 따라서 집합의 최소성이 보장된다. (하지만 알고리즘의 시작 상태나 노드를 고려하는 순서에 따라 최종 커버 집합의 크기는 달라질 수 있다. '최소 크기'가 보장되는 것은 아니라는 것이다. -> C의 어떤 노드를 하나라도 제거하면 더이상 k-Path를 커버하지 못하게 되는 의미의 최소)

 

4-2. Lower Bounds

계산된 답의 품질을 평가하기 위한 하한을 어떻게 도출할 것인가.

일단 k-Path 중에서 서로 노드를 공유하지 않는 경로들의 집합을 최대한 많이 찾는다.

그래프에서 k-Path를 탐욕적으로 선택하되, 이전에 선택한 경로와 노드를 공유하지 않는 경로만을 선택하는 것이다. 

그럼 커버집합 C는 이 각각의 경로로부터 하나 이상의 노드를 포함해야 한다. 즉, C의 크기는 위의 서로소인 k-Path 개수보다 작을 수 없다. 

이 k-Path 개수를 하한으로 두면 이 알고리즘이 찾은 커버가 최적 해에 꽤 가깝다는 것을 실험적으로 알 수 있다. 

 

4-3. Nested k-Path Cover

경로 시각화 시 k-Path Cover를 중첩하여 사용하는 것의 중요성을 설명한다.

특히, 위 예시에 나왔던 확대/축소 시 경로 표현의 일관성을 유지하기 위해 말이다.

중첩 k-Path Cover는, 단순 하나의 k-Path Cover를 의미하는 것이 아닌, 서로 다른 여러 개의 k값에 대해 계산된 k-Path Cover 집합들이 특정한 포함 관계를 만족하는 집합들의 연속을 말한다.

단일 k값에 대한 cover만으로는 다양한 적용에서의 최적의 성능을 달성하기 어렵기에 다양한 k값에 대한 cover를 미리 준비해두고 요구에 가장 적합한 k값을 선택하여 사용할 수 있게 된다.

 

4.4 Overlay-Graph Construction

오버레이 그래프는 원본 그래프에서 핵심 노드들 간의 연결성을 요약한 것이다.

일단 원본 그래프의 정점 집합 중 k-Path Cover를 계산 후, 이 C 집합에 속한 노드들이 오버레이 그래프의 정점이 된다.

간선은 다음과 같은 규칙을 따라 생성된다. 

두 노드 v, w가 모두 C에 속해야 하며, 원본 그래프 G에서 v->w 경로가 존재해야 한다.

결정적으로, v->w 상에 있는 다른 어떤 노드도 커버 집합 C에 속해서는 안된다. 

이렇게 구성된 오버레이 그래프는 원본 그래프의 복잡성은 줄이고, C의 노드들 간의 중요한 연결 정보를 유지할 수 있다. 

따라서 계산 속도를 높이는 데 사용된다.

 

4.5 Special, k-Shortest-Path Cover

k-SPC는 G에서 특정 '가중치'에 따라 계산된 k개로 구성된 최단 경로에 대해 하는 것.. 가중치에 대한 최단 경로를 따짐.

따라서 최단 경로가 아닌 k-Path는 커버할 필요가 없다. 즉, k-PC보다는 다루는 경로의 수가 적음!

 

Quick Pruning은, k-SPC 문제에 맞게 속도를 개선한 변형이다. 집합 최소성을 보장하지는 않는다.

그 이유는 A와 가까이 있다고 해서 일단 B 노드를 선택하고, 이후 B->C 경로를 선택 후,

이 길이가 k 노드 이상이고 또다른 C의 노드에 의해 커버되지 않는다면? 노드 B가 Cover에 필요하다고 판단하게 될 것이다.

하지만 이때 A->C의 경로가 A->B->C 보다 짧다면? B를 포함한 경로가 최단 경로가 아님에도 B를 Cover에 포함시킨 것이 된다.

'v에서 시작하는 최단 경로 트리'와 'v로 끝나는 역방향 최단 경로 트리'를 구성하여, 두 최단 경로 조각을 v에서 합쳐 길이가 k이상인 경로가 있는지를 확인한다. 있다면 v를 C에 포함!

 

Quick Pruning 알고리즘이 빠르게 작동하는 이유

- 가지치기 결정 과정 : v를 C에서 제거할 수 있는지 판단을 위해 노드와 관련한 순/역방향 탐색 진행

- 조기 종료 조건 : 그래프 전체 탐색이 아님. C에 포함된 다른 노드에 도달한다면 즉시 종료

 

5. Experimental Evaluation

이 논문의 pruning 방식은 adaptive sampling 및 quick pruning보다 더 작은 k-SPC 커버를 생성할 수 있음을 증명.

실행 시간 측면에서는, Quick Pruning < Adaptive Sampling < Pruning

 

C의 품질을 평가하는 한 가지 지표로, '이웃 노드 간의 홉 거리'를 설명한다.

홉 거리는 두 노드 사이 최단 경로에 포함된 엣지의 수 인데, C에서 이웃 노드 간 홉 거리가 크다는 것은?

C에 포함되지 않은 원래 그래프 G의 많은 노드들이 C에 의해 커버되고 있음을 말한다.

즉 C에 포함되지 않은 노드들로만 이루어진 짧은 경로는 존재하기 어렵다는 것이다.

 

이것이 어떻게 평가 지표로 작용하느냐면, 

이웃 노드 간 홉 거리가 크다는 것은 C가 원래 그래프 G를 더 효율적으로 요약하거나 표현하고 있다는 것.

그래서 오버레이 그래프를 만들 때, 이웃 노드 간 홉 거리가 길수록 더 많은 정보를 압축하고 있다는 뜻이 된다.

 

기존 방식들은 다수의 메트릭을 고려했는데, 이 논문은 그의 비효율성 문제를 해결하기 위해 k-Path Cover 활용 새로운 방식을 제안한다.

사용자가 출발지 및 목적지 뿐만 아니라 개인적 선호도에 따라 다양한 요소의 가중치를 직접 지정할 수 있게 하는데,

각 경로 탐색 쿼리마다 고유한 가중치 집합을 적용할 수 있다는 것이 중요한 특징이다.

기존 방식은 고정된 가중치에 의존하여 가중치가 변경될 경우 전처리를 다시 하거나 상당한 시간이 소요되는데, 

해당 논문의 방식은 쿼리 시점에 가중치 변화를 효율적으로 처리할 수 있다.

 

전처리

k-APC C를 이용해 오버레이 멀티그래프를 구성하는 방법, 개인 맞춤 길찾기를 더 빠르게 하는 방법

1. 중요 지점만 골라내고,

2. 중요 지점들 사이 다른 중요 지점을 거치지 않고 두 지점을 잇는 고속 링크 간선을 그려 이를 잇는다

3. 고속 링크 비용을 합산하여 저장한다.

4. 개인 맞춤 길찾기는 이 고속 링크 지도에서 시행한다.

 

쿼리 처리 과정

1. 출발 노드 s->C까지의 초기 탐색 - 우선순위 큐에 남아 있는 모든 노드의 s로부터의 최단 경로가 최소 하나 이상의 C 노드를 포함하게 될 때까지

2. 목표 노드 t->C까지의 역방향 탐색

3. 오버레이 그래프 GO 에서의 탐색 및 최종 경로 결정

 

|v|가 큰 원본 그래프 G에서 직접 경로를 찾는 대신, 노드 수가 훨씬 적은 오버레이 멀티 그래프 GO 에서 대부분의 탐색을 수행하고, 오버레이 그래프에 진입/탈출하기 위한 짧은 초기 탐색만 필요하기에 전체 쿼리 처리가 매우 효율적이다.

 

그리고 보통 개인화 경로 질의 처리 시 '오버레이 다중 그래프에서의 탐색'이 전체 질의 시간을 지배한다. 

따라서 이 방법의 효율성은 대부분의 쿼리 시간을 GO같은 그래프에서 탐색하는 데 할애한다.

 

6. 결론

k-APC 문제를 소개하며, 이에 대한 해결 방안인 Pruning 알고리즘을 제안한다.

또한 k-SPC 문제에 대한 상당한 개선을 이루었다.

개인화된 경로 계획 프레임워크도 개발되었으며, 향후 더 빠른 응답 시간을 목표로 한다. 

이와 함께 다른 가속 기법과의 결합 가능성도 생각해본다.