Hop Doubling Label Indexing for Point-to-Point DistanceQuerying on Scale-Free Networks

본 게시글은 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks, Minhao jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, Yanyan Xu를 읽고 작성한 글입니다.

 

1. Title

Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks

 

2. Abstract

P2P 거리 질의 문제에서 (무)방향성 그래프가 주어졌을 때, hop-doubling 라벨링 기술 기반 질의 응답 인덱스 구축 제안

가중치 없는 스케일-프리 그래프 속성을 기반으로 인덱스 크기, 계산 비용 및 I/O 비용에 대한 경계 도출

*hop-doubling labeling : 그래프 각 노드에 라벨을 붙여 인덱스를 구축. 이 라벨은 특정 규칙에 따라 생성되고, 불필요 정보를 제거.

 

기존 기술보다 질의시간/인덱싱 비용 측면에서 효율적/효과적임. 또한 매우 큰 그래프도 처리 가능.

 

즉, 복잡한 연결 구조를 가진 대규모 네트워크에서 길 찾기를 더 빠르고 효율적으로 할 수 있는 새로운 인덱싱 기술 제안

 

3. 목표

'대규모 스케일-프리 그래프'에서 두 노드간 최단 거리를 효율적으로 찾는 인덱싱 기법 개발

 

4. 방법

(1) 홉-더블링 라벨링

각 노드에 라벨 할당으로 인덱스 구축 (라벨은 특정 규칙에 따라 생성, 불필요한 정보는 가지치기로 제거)

Trough path 개념 도입으로 불필요한 라벨 생성 억제

순위가 max(rank(u), rank(v)보다 낮은 노드로만 이루어지도록 하는 것. U자라고 생각하면 될 듯

hop-stepping 전략으로 초기 단계에서 라벨 크기의 급격한 증가를 막고, 홉-더블링으로 전환해 빠른 수렴 유도

 

* 인덱스 구축 : 주어진 두 노드 사이 최단 거리 빠르게 찾기 가능, 다양한 곳(페이지 유사도, 키워드 검색 등)에 활용 가능

* Trough path : 노드 degree(연결 엣지 수)에 따른 rank를 정해서, 두 노드 u와 v를 잇는 경로를 결정할 때, 경로상 모든 노드의 

* 불필요한 라벨 생성 억제 : 높은 degree의 노드들은 다른 노드들간의 최단 경로에 포함될 가능성이 높아서, 다른 노드들 간의 최단 경로에 포함될 가능성이 낮은, 낮은 degree의 노드들만을 고려하는 것 

* hop-doubling : 경로의 홉 수(엣지 수, a->b->c라면 홉 수는 2)를 두 배씩 늘림(1홉, 2홉, 4홉, 8홉,...) -> 초기 단계에서 라벨 크기가 급격히 증가할 수 있음 (홉 수가 증가할수록 각 노드가 알아야 할 정보, 즉 라벨에 저장해야 할 정보다 많아져서 라벨 크기가 증가하는 것), 빠르게 더 먼 거리의 노드 간 정보를 라벨에 담을 수 있어 좋음.

* hop-stepping : 경로의 홉 수를 1씩 늘림

 

(2) 스케일-프리 그래프 특성 활용

멱법칙 분포 특성을 이용해 인덱스 크기, 계산 비용, I/O 비용 감소

hub dimension 및 hitting set 개념 도입으로 라벨 크기 제한

degree가 매우 높은 소수의 '허브 노드'들이 존재하며, 그래프 내 임의의 두 노드 간 평균 최단 경로 길이가 짧다.

 

* 멱법칙 분포 : 어떤 현상의 빈도가 그 크기에 반비례하는 관계로, 엣지 수의 분포가 멱법칙을 따른다면 스케일-프리 그래프이다.

* hitting set : 주어진 경로들의 집합 P에 대해, P에 속한 모든 경로가 적어도 하나의 노드를 포함하는 노드들의 집합

* hub dimension : 그래프 내 모든 노드에 대해, 노드들을 지나는 최단 경로들을 커버하는 히팅 셋의 최소 크기

 

(3) I/O 효율적인 알고리즘 설계

메모리를 고려해 디스크 기반 작동 알고리즘 개발

nested loop join 방식을 응용해 후보 라벨 생성 및 가지치기 수행

 

5. 결과

더 큰 그래프 처리 가능함 입증, hopdb는 더 작은 인덱스 크기를 가지며 질의 처리 속도가 더 빠르다.