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

다국어 초록 (Multilingual Abstract)

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.

국문 초록 (Abstract)

도로 네트워크(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는 기존의 연구에서도 그 효율성이 입증되었으며, 본 논문에서의 실험에서 도로 네트워크에 대해서도 우수한 성능을 보였다.

참고문헌 (Reference)

• 1 T. Abeywickrama, "k-nearest neighbors on road networks : a journey in experimentation and in-memory implementation" 9 (9): 492-503, 2016
• 2 L. v. d. Maaten, "Visualizing Data using t-SNE" 9 : 2579-2605, 2008
• 3 L. Cohen, "The FastMap algorithm for shortest path computations" 1427-1433, 2018
• 4 V. D. Silva, "Sparse multidimensional scaling using landmark points" Stanford University 2004
• 5 Y. Manolopoulos, "R-Trees:Theory and Applications" Springer 2005
• 6 "Pruned Highway Labeling Github"
• 7 H. -P. Kriegel, "Proximity queries in large traffic networks" 21-, 2007
• 8 I. Borg, "Modern Multidimensional Scaling: Theory and Applications" Springer 2007
• 9 Y. Zhou, "Massively parallel a*search on a GPU" 1248-1254, 2015
• 10 P. Ciaccia, "M-tree:An Efficient Access Method for Similarity Search in Metric Spaces" 426-435, 1997
• 11 H. -P. Kriegel, "Hierarchical Graph Embedding for Efficient Query Processing in Very Large Traffic Networks" 150-167, 2008
• 12 V. D. Silva, "Global versus local methods in nonlinear dimensionality reduction" 16 : 721-728, 2003
• 13 Y. Li, "Flexible aggregate similarity search" 1009-1020, 2011
• 14 B. Yao, "Flexible Aggregate Nearest Neighbor Queries in Road Networks" 761-772, 2018
• 15 C. Faloutsos, "FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets" 163-174, 1995
• 16 J. C. Platt, "FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms" 261-268, 2005
• 17 T. Akiba, "Fast shortest-path distance queries on road networks by pruned highway labeling" 147-154, 2014
• 18 "Eigen C/C++ Template Library for Linear Algebra"
• 19 K. Shaw, "Efficient Approximation of Spatial Network Queries using the M-Tree with Road Network Embedding" 11-11, 2007
• 20 E. Ioup, "Efficient AKNN spatial network queries using the M-Tree" 46-, 2007
• 21 "DIMACS Implementation Challenge"
• 22 D. Papadias, "Aggregate nearest neighbor queries in spatial databases" 30 (30): 529-576, 2005
• 23 M. L. Yiu, "Aggregate nearest neighbor queries in road networks" 17 (17): 820-833, 2005
• 24 I. Abraham, "A hub-based labeling algorithm for shortest paths in road networks" 230-241, 2011