도로 네트워크에서 이동 객체를 위한 시공간 유사 궤적 검색 알고리즘 = Trajectory Search Algorithm for Spatio-temporal Similarity of Moving Objects on Road Network

국문 초록 (Abstract)

모바일 환경의 대중화와 이를 위한 기반 기술의 발전으로 인하여 이동 객체들을 효과적으로 표현하고 분석하는 것이 중요한 문제로 대두되고 있다. 이러한 환경에서 이동 객체 궤적의 유사성 검색은 궤적에 대한 데이터 마이닝의 일부분으로 중요한 연구 분야중의 하나이다. 본 논문에서는 도로 네트워크상의 이동 객체 궤적을 위한 시공간 유사 궤적 검색 알고리즘을 제안한다. 이를 위하여 도로 네트워크상에서 두 이동 객체 궤적 사이의 시공간 거리를 정의하고, 이를 기반으로 궤적 사이의 시공간 유사도 측정 방법을 제안한다. 유사 궤적 알고리즘은 효율적인 검색을 위하여 시그니쳐 파일 기법을 이용하여 궤적을 검색한다. 마지막으로, 본 논문에서 제안하는 시공간 유사 궤적 검색 알고리즘을 구현하고, 성능 분석을 통해 제안하는 알고리즘의 효율성을 입증한다.

다국어 초록 (Multilingual Abstract)

Advances in mobile techknowledges and supporting techniques require an effective representation and analysis of moving objects. Similarity search of moving object trajectories is an active research area in data mining. In this paper, we propose a trajectory search algorithm for spatio-temporal similarity of moving objects on road network. For this, we define spatio-temporal distance between two trajectories of moving objects on road networks, and propose a new method to measure spatio-temporal similarity based on the real road network distance. In addition, we propose a similar trajectory search algorithm that retrieves spatio-temporal similar trajectories in the road network. The algorithm uses a signature file in order to retrieve candidate trajectories efficiently. Finally, we provide performance analysis to show the efficiency of the proposed algorithm.

참고문헌 (Reference)

1 "？Translation invariant mixture models for curve clustering,？" 79-88, 2003

2 "？The camera mouse: visual tracking of body features to provide computer access for people with severe disabilities,？" 10 (10): 1-10, 2002

3 "？Systematic detection of subtle spatio-temporal patterns in time-lapse imaging,？" 6 (6): 71-78, 1998

4 "？Spatio-temporal Similarity Analysis Between Trajectories on Road Networks,？" 280-289, 2005

5 "？Similar Sub-Trajectory Retrieval for Moving Objects in Spatio-temporal Databases,？" 308-322, 2003

6 "？Signature Files: An Access Method for Documents and Its Analytical performance Evaluation,？" 2 (2): 267-288, 1984

7 "？Shapes Based Trajectory Queries for Moving Objects ？" 21-30, 2005

8 "？Shape-Based Similarity Query for Trajectory of Mobile Objects？ Conference on Mobile Data Management" 63-77, 2003

9 "？Shape-Based Similarity Query for Trajectory of Mobile Objects？" 63-77, 2003.

10 "？Robust and fast similarity search for moving object trajectories ？" 491-502, 2005

11 "？Robust Similarity Measures for Mobile Object Trajectories,？" 721-728, 2002

12 "？Novel Approaches in Query Processing for Moving Object Trajectories ？" 395-406, 2000

13 "？Mobile computing and databases？a survey,？" 11 (11): 108-117, 1999

14 "？Inverted Files versus Signature Files for Text Indexing,？" 23 (23): 453-490, 1998

15 "？Interactive motion generation from examples ？ In Proc. of ACM SIGGRAPH" 483-490, 2002

16 "？FTW: Fast similarity search under the time warping distance,？" 326-337, 2005

17 "？Distributed Spatio- Temporal Similarity Search,？" 14-23, 2006

18 "？Discovery of correlation from multi-stream of human motion,？" 290-294, 2000

19 "？Discovering Similar Multidimensional Trajectories,？" 673-684, 2002

20 "？An Updated Bibliography of Temporal, spatial and spatio-temporal data mining Research,？" TSDM 147-164, 2000

21 "？An Efficient Indexing Scheme for Moving Objects？Trajectories on Road Networks,？" WAIM 13-25, 2006

22 "？A Framework for Generating Network-Based Moving Objects,？" 6 (6): 153-180, 2002