도로 위에 존재하는 이동객체의 궤적에 대한네트워크 기반의 색인 방법
A Network-based Indexing Method for Trajectories of Moving Objects on Roads
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최근 많은 연구들이 유클리디안 공간을 기반으로 대용량의 이동객체 궤적 데이터를 효율적으로 다루기 위해 진행되어 왔다. 그러나, 일반적으로 실제 응용분야에서는 이동객체가 움직일 수 있는 공간은 제한적이다. 예를 들어, 도로 위에 존재하는 자동차들은 서로 연결된 도로망을 통해서만 이동할 수 있다. 본 논문에서는 도로 위의 이동객체 궤적에 대하여 시공간 영역 질의를 처리할 수 있는 네트워크 기반의 색인방법을 제안한다. 제안된 방법은 질의 처리 과정에서 네트워크 상의 거리를 이용하기 위해서 도로 네트워크의 연결정보를 색인구조에 포함한다. 그리고, 이동객체의 위치 정보를 도로를 구성하는 도로 선분요소 정보를 이용하여 표현하고 이를 단위로 여러 개의 R-tree를 사용하여 이동객체 궤적들을 관리한다. 또한, 여러 개의 도로 선분요소 사이에 하나의 R-tree를 공유할 수 있는 구조를 가짐으로써, 큰 도로 네트워크 데이터에서도 적용할 수 있다. 우리는 실험을 통해서 네트워크 거리를 기반으로 시공간 영역질의를 처리하는 것은 기존의 유클리디안 거리 기반의 방법들보다 대략 30%의 성능향상을 보임을 보여준다.
Abstract
Recently many researchers have focused on management of historical trajectories of moving objects in Euclidean spaces due to numerous sizes of accumulated data over time. However, the movement of moving objects in real applications generally has some constraints, for example vehicles on roads can only travel along connected road networks. In this paper, we propose an indexing method for trajectories of moving objects on road networks in order to process the network-based spatiotemporal range query. Our method contains the connect information of road networks to use the network distance for query processing, deals with trajectories which are represented by road segments in road networks, and manages them using multiple R-trees assigned per each road segment. Furthermore, it has a structure to be able to share R-tree among several road segments in large road networks. Consequently, we show that our method takes about 30% less in node accesses for the network-based spatiotemporal range query processing than other methods based on the Euclidean distance by experiments.
참고문헌 (20)
- S. Saltenis, "Indexing the Positions of Continuously Moving Objects", pp.331~342 (2000)
- A. Guttman, "R-trees a dynamic index structure for spatial searching", pp.4757~ (1984)
- Y. Theodoridis, "Spatio-Temporal Indexing for Large Multi- media Applications", pp.441~448 (1996)
- M. Nascimento, "Towards historical R-trees", pp.235~240 (1998)
- Y. Tao, "MV3R-Tree:A Spatio-Temporal Access Method for Timestamp and Interval Queries", pp.431~440 (2001)
- D. Pfoser, "Novel Approaches in Query Processing for Moving Object Trajectories", pp.395~406 (2000)
- V. P. Chakka, "Indexing Large Trajectory Data Sets with SETI", pp.164~175 (2003)
- Z. Song, "An approach to Index continuously moving objects", pp.340~344 (2003)
- M. Vazirgiannis, "A Spatiotemporal Model and Language for Moving Objects on Road Networks", pp.2535~ (2001)
- L. Speicys, "Computational Data Modeling for Network-Constrained Moving Objects", pp.118~125 (2003)
- C. Shahabi, "A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases", pp.94~100 (2002)
- C. S. Jensen, "Nearest Neighbor Queries in Road Networks", pp.18~ (2003)
- D. Pfoser, "Indexing of Network-Constrained Moving Objects", pp.25~32 (2003)
- E. Frentzos, "Indexing objects moving on Fixed networks", pp.289~305 (2003)
- V. de Almeida, "Indexing the Trajectories of Moving Objects in Networks", pp.115~118 (2004)
- H. D. Chon, "Query Processing for Moving Objects with Space-Time Grid Storage Model", pp.121~130 (2002)
- D. Papadias, "Query Processing in Spatial Network Databases", pp.802~813 (2003)
- P. Scarponcini, "Generalized Model for Linear Referencing in Transportation", 6(1), pp.35~55 (2002)
- S. Shekhar, "CCAM : A Connectivity-Clustered Access Method for Networks and Network Computations", 9(1), pp.102~119 (1997)
- T. Brinkhoff, "A framework for generating network-based moving objects", 6(2), pp.153~180 (2002)