대용량 로드네트워크에서 효율적인 프리겔 기반의 최단경로 색인 기법 (Efficient Pregel based Shortest Path Indexing in Large Road Networks)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 31권 / 3호 / 83 ~ 97페이지
· 저자명 : 김현욱, 김태연, 박기성, 한용구, 이영구

초록

최근 대용량의 로드네트워크 데이터를 이용하여 다양한 위치 기반 서비스를 제공하는 기술이 널리 활용되고 있다. 최단경로 탐색은 로드네트워크 데이터에서 사용자에게 최적의 이동 경로 등을 제공하는 가장 기본적인 연산이다. 기존의 최단경로 색인 기법은 대용량의 로드네트워크에서 비효율적인 수행시간과 메모리 공간을 요구한다. 최근 로드네트워크 데이터를 여러 개의 독립적인 그리드 셀로 나누고, 그리드 내의 중요한 지역에 대하여 최단 세그먼트를 사전에 구축한 AH(arterial hierarchy)기법이 제안되었다. AH는 최단 세그먼트를 이용하여 각 그리드 셀을 병합하며 효율적으로 최단경로를 색인한다. 본 논문에서는 프리겔(pregel)을 이용하여 대용량 로드네트워크의 효율적인 최단경로 색인 기법을 제안한다. 제안하는 기법은 로드네트워크를 그리드 셀 단위로 분할하고, 그리드 셀 내의 중요 지점에 대한 최단 세그먼트 계산을 병렬 처리한다. 성능평가를 통하여 제안하는 기법이 기존의 AH보다 최대 75%의 성능 향상 결과를 보인다.

영어초록

Recently, location based services using massive road network data are widely used. The shortest path indexing is an essential operation to provide an optimal moving path for users. The classic solution for the shortest path indexing requires inefficient running time and memory space for large road networks. Recently, Arterial Hierarchy(AH) has been proposed, which divides a road network into grid cells and pre-computes shortest segments for important points. AH efficiently construct indexes to the shortest path by combining the grid cells using the shortest segments. In this paper, we propose an efficient Pregel based shortest path indexing method for large road networks. The proposed method divides a road network into grid cells and performs distributed processing of shortest segments for important points in each cell. Our experimental results show that the proposed method can reduce running time for the shortest path indexing by up to 75% compared with the existing AH.

참고자료

· 없음