데이터베이스 연구회지(SIGDB)
Current Result Document :
| 한글제목(Korean Title) |
대용량 로드네트워크에서 효율적인 프리겔 기반의 최단경로 색인 기법 |
| 영문제목(English Title) |
Efficient Pregel based Shortest Path Indexing in Large Road Networks |
| 저자(Author) |
김현욱
Hyunwook Kim
김태연
Taeyeon Kim
박기성
Kisung Park
한용구
Yongkoo Han
이영구
Young-Koo Lee
|
| 원문수록처(Citation) |
VOL 31 NO. 03 PP. 0083 ~ 0097 (2015. 12) |
한글내용
(Korean Abstract) |
최근 대용량의 로드네트워크 데이터를 이용하여 다양한 위치 기반 서비스를 제공하는 기술이 널리 활용되고 있다. 최단경로 탐색은 로드네트워크 데이터에서 사용자에게 최적의 이동 경로 등을 제공하는 가장 기본적인 연산이다. 기존의 최단경로 색인 기법은 대용량의 로드네트워크에서 비효율적인 수행시간과 메모리 공간을 요구한다. 최근 로드네트워크 데이터를 여러 개의 독립적인 그리드 셀로 나누고, 그리드 내의 중요한 지역에 대하여 최단 세그먼트를 사전에 구축한 AH(arterial hierarchy)기법이 제안되었다. AH는 최단 세그먼트를 이용하여 각 그리드 셀을 병합하며 효율적으로 최단경로를 색인한다. 본 논문에서는 프리겔(pregel)을 이용하여 대용량 로드네트워크의 효율적인 최단경로 색인 기법을 제안한다. 제안하는 기법은 로드네트워크를 그리드 셀 단위로 분할하고, 그리드 셀 내의 중요 지점에 대한 최단 세그먼트 계산을 병렬 처리한다. 성능평가를 통하여 제안하는 기법이 기존의 AH보다 최대 75%의 성능 향상 결과를 보인다.
|
영문내용
(English Abstract) |
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.
|
| 키워드(Keyword) |
최단경로 색인 기법
프리겔 프레임워크
대용량 로드네트워크
shortest path indexing
Pregel framework
large road networks
|
| 파일첨부 |
PDF 다운로드
|
