도로 네트워크에 대한 다차원 척도법의 비교 (Comparison of Multidimensional Scaling Methods for Road Networks)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 36권 / 2호 / 3 ~ 16페이지
· 저자명 : 노웅기

초록

도로 네트워크(road network)는 실세계 도로 상의 관심 지점들(points of interest, POIs)과 그들 간의 교통 상황을 반영한다. 도로 네트워크 응용은 매우 다양하며, 이러한 응용에서는 근접성 검색(proximity search)를 비롯하여, 집계 최근접 객체(aggregated nearest neighbor, ANN) 검색, 유연한 집계 최근접 객체(flexible aggregated nearest neighbor, FANN) 검색 등이 발생한다. 도로 네트워크 내의 두 POI 간의 거리는 그들 간의 최단경로 거리(shortest-path distance)로 정의되며, 이 연산은 유클리드 공간 내의 두 지점 간의 거리 계산에 비하여 복잡도가 매우 높다. 도로 네트워크 내의 각 POI는 거리 공간(metric space) 내의 하나의 객체로 대응이 가능하다. 만약 도로 네트워크 내의 POI를 그들 간의 거리가 유지되도록 유클리드 공간으로 매핑이 가능하다면 기존의 R-트리 등에 기반한 알고리즘들을 활용할 수 있으며, 두 POI 간의 거리 계산 비용도 크게 낮아질 것이다. 본 논문에서는 도로 네트워크에 대하여 전통적 MDS (classical MDS), 랜드마크 MDS (landmark MDS, LMDS), 그리고 FastMap 세 가지 다차원 척도법(multidimensional scaling, MDS) 방법들을 적용하여 유클리드 공간으로의 변환 시간 및 품질을 비교한다. 이 중 LMDS는 기존의 연구에서도 그 효율성이 입증되었으며, 본 논문에서의 실험에서 도로 네트워크에 대해서도 우수한 성능을 보였다.

영어초록

A road network consists of points of interest (POIs) and the traffic situations between them in the real world. There are a number of road network applications; they issue many proximity queries, aggregated nearest neighbor (ANN) queries, and flexible aggregated nearest neighbor (FANN) queries. The distance between two POIs in a road network is defined as the shortest-path distance between them, and the computation of the distance has a complexity that is much higher than that of distance computation in a Euclidean space. Each POI in a road network corresponds to an object in a metric space. If the POIs are mapped into the points in a Euclidean space such that their distances are preserved as much as possible, we can harness the existing algorithms using multidimensional index structures like the R-trees and significantly reduce the cost of distance computations when processing diverse queries. In this study, we consider three multidimensional scaling (MDS) methods, namely classical MDS, landmark MDS (LMDS), and FastMap, for mapping POIs in a road network into points in a Euclidean space, and compare the execution time and mapping quality of these methods. Among the methods, LMDS has been proven to be highly efficient in previous studies, and our experiments also demonstrated fast execution and high mapping quality of LMDS for road networks.

참고자료

· 없음