시공간 유사성을 이용한 도로 네트워크 상의 유사한 궤적 검색 = Similar Trajectory Retrieval on Road Networks using Spatio-Temporal Similarity

국문 초록 (Abstract)

이동 객체들의 행동을 분석하기 위해서는 그 이동 객체 궤적들 간의 유사성 측정을 정의하는 것이 필요하다. 비록 유클리디언 공간 상에서 이동 객체들의 유사한 궤적들을 검색하는 몇몇 연구가 있었지만, 도로 네트워크 공간 상에서 이동 객체들의 궤적에 대한 유사성 연구는 거의 관심을 끌지 못 했다. 실제 응용에서, 대부분의 이동 객체들은 유클리디언 공간보다 도로 네트워크 공간 상에 존재한다. 그러나 궤적들 간의 유사성 측정에서, 기존의 방법들은 유클리디언 거리를 기반으로 하고 있으며, 오직 공간적 유사성만을 고려하고 있다. 본 논문에서, 우리는 도로네트워크 상에서 POI와 TOI를 기반으로 유사성 측정을 정의한다. 이러한 정의를 바탕으로, 우리는 궤적들 간의 시공간 유사성을 사용하여 유사한 궤적을 검색하는 방법들을 제시한다. 그리고 유사한 궤적들에 대하여 클러스터링을 수행한 결과를 보인다. 실험 결과는 각 방법에 의해 검색된 유사한 궤적들과 그 검색된 궤적 결과들이 각 방법 간에 얼마나 일치하는지를 보인다.

다국어 초록 (Multilingual Abstract)

In order to analyze the behavior of moving objects, a measure for determining the similarity of trajectories needs to be defined. Although research has been conducted that retrieved similar trajectories of moving objects in Euclidean space, very little research has been conducted on moving objects in the space defined by road networks. In terms of real applications, most moving objects are located in road network space rather than in Euclidean space. In similarity measure between trajectories, however, previous methods were based on Euclidean distance and only considered spatial similarity. In this paper, we define similarity measure based on POI and TOI in road network space. With this definition, we present methods to retrieve similar trajectories using spatio-temporal similarity between trajectories. We show clustering results for similar trajectories. Experimental results show that similar trajectories searched by each method and consistency rate between each method for the searched trajectories.

참고문헌 (Reference)

1 "이동객체의 궤적에 대한 연속 최근접 질의 처리" 31 (31): 492-504, 2004.10.

2 "Similarity Measures for Mobile Object Trajectories" 721-728, 2002.

3 "Similar Sub-TrajectoryRetrieval for Moving Objects in Spatio-temporal Databases" Springer-Verlag 308-322, 2003.

4 "Shape-Based Similarity Query for Trajectory of Mobile Objects" Springer-Verlag 63-77, 2003.

5 "Robust and Fast Similarity Search for Moving Object Trajectories" 491-502, 2005.

6 "Representation of Moving Objects along a Road Network" 187-194, 2004.

7 "Representation in Location-based Services : Problems & Solution" 2003.

8 "Query Processing in Spatial Network Databases" 802-813, 2003.

9 "Project Lachesis: Parsing and Modeling Location Histories" Springer-Verlag 106-124, 2004.

10 "Novel Approaches in Query Processing for Moving Object Trajectories" 395-406, 2000.

11 "Nearest Neighbor Queries in Road Networks" 1-8, 2003

12 "Modeling Moving Objects over Multiple Granularities" 36 : 177-194, 2002.

13 "High Dimensional Similartity Search with Space Filling Curves" 615-622, 2001.

14 "Discovering Similar Multidimensional Trajectories" 673-684, 2002.

15 "Computational Data Modeling for Network-constrained Moving Objects" 118-125, 2003.

16 "Clustering by Pattern Similarity in Large Data Sets" ACM Press 394-405, 2002.

17 "BIRCH : An Efficient Data Clustering Method for Very Large Databases" ACM Press 103-114, 1996.

18 "Aggregate Nearest Neighbor Queries in Road Networks" 17 (17): 820-833, 2005.

19 "A Spatiotemporal Model and Language for Moving Objects on Road Networks" Springer-Verlag 20-35, 2001.

20 "A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases" 94-100, 2002.