이동 객체 궤적의 색인을 위한 개선된 분할 알고리즘
An Improved Split Algorithm for Indexing of Moving Object Trajectories
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최근 GPS, 이동 전화, 무선 네트워크 등의 발달로 인해 넓은 공간상에서 시간의 흐름에 따라 변화하는 이동 객체에 대한 위치 정보를 수집하여 실생활에 활용하는 다양한 위치 기반 서비스의 사용이 늘어나고 있다. 그와 함께 대용량의 이동 객체를 빠르게 검색하기 위한 효율적인 색인 방법의 필요성이 대두 됨에 따라 관련된 많은 연구가 현재 진행 중이다. 본 논문에서는 이동 객체의 궤적에 대한 색인 과정에서 필요한 개선된 궤적 분할 방법을 제안한다. 궤적의 적절한 분할 위치를 찾아 근사치 영역을 나타내는 최소 경계 사각형(MBR)을 만드는 과정에서 평균적인 질의의 크기를 고려하여 형성되는 확장된 최소 경계 사각형(EMBR)의 영역을 이용한다. 이에 따라 EMBR의 총면적이 최소에 가까운 분할을 만들어내어 색인 구성 후 질의 수행 과정 동안에 불필요한 탐색 공간을 감소시키는 이점을 보이게 된다. 본 논문에서 제안하는 궤적 분할 방법의 우수성을 입증하기 위해 최적의 궤적 분할 방법과 기존의 궤적 분할 방법을 구현하여 각각의 EMBR 면적을 비교 분석한다. 비교 결과 제안하는 궤적 분할 방법이 기존의 방법보다 최적의 분할에 더 가까운 EMBR의 총면적을 나타내는 것을 알 수 있었다.
Abstract
Recently, use of various position base servicesthat collect position information for moving object and utilize in real life is increasing by the development of wireless network technology. Accordingly, new index structures are required to efficiently retrieve the consecutive positions of moving objects. This paper addresses an improved trajectory split algorithm for the purpose of efficiently supporting spatio-temporal range queries using index structures that use Minimum Bounding Rectangles(MBR) as trajectory approximations. We consider volume of Extended Minimum Bounding Rectangles (EMBR) to be determined by average size of range queries. Also, Use a priority queue to speed up our process. This algorithm gives in general sub-optimal solutions with respect to search space. Our improved trajectory split algorithm is going to derive minimizing volume of EMBRs better than previously proposed split algorithm.
참고문헌 (21)
- M. F. Mokbel, "Spatio-Temporal Access Methods", Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, pp.40~49 (2003)
- D. L. Lee, "Data Management in Location-Dependent Information Services", IEEE Pervasive Computing, pp.65~72 (2002)
- D. Pfoser, "Novel Approaches to the Indexing of Moving Object Trajectories", Proc of The 26thInternational Conference on Very Large Data Bases, pp.395~406 (2000)
- S. Rasetic, "A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing", Proc of The 31st International Conference on Very Large Data Bases, pp.934~945 (2005)
- X. Xu, "RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases", Proc of the International Symposium on Spatial Data Handling, pp.1040~1049 (1990)
- Y. Theodoridis, "Spatio- Temporal Indexing for Large Multimedia Applications", Proc of the 3rd IEEE International Conference on Multimedia Computing and Systems, pp.441~448 (1996)
- O. Wolfson, "Location Management in Moving Objects Databases", Proc of the International Workshop on Satellite-Based Information Services, pp.7~14 (1997)
- T. Brinkhoff, "Generating Network-Based Moving Objects", Proc of the International Conference on Scientific and Statistical Database Management, pp.253~255 (2000)
- R. Benetis, "Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects", Proc of the International Symposium on Database Engineering and Applications, pp.44~53 (2002)
- M. Hadjieleftheriou, "Efficient indexing of Spatiotemporal Objects", Proc of The 8th International Conference on Extending Database Technology, pp.251~268 (2002)
- D. E. KNUTH, "The Art of Computer Programming, Volume 3, Sorting and Searching Second Edition" (1998), Addison Wesley Longman
- J. Nievergelt, "The Grid File: An Adaptable, Symmetric Multikey File Structure", ACM Transactions on Database Systems, pp.38~71 (1984)
- T. Tzouramanis, "Overlapping linear quadtrees: a spatio-temporal access method", Proc of the 6th International Symposium on Advances in Geographic Information Systems, pp.1~7 (1998)
- A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching", Proc of the ACM International Conference on Management of Data, pp.47~57 (1984)
- Y. Theodoridis, "On the Generation of Spatiotemporal Datasets", Proc of the 6th International Symposium on Spatial Databases, pp.147~164 (1999)
- Z. Song, "SEB-tree: An Approach to Index Continuously Moving Objects", Proc of the 4th International Conference on Mobile Data Management, pp.340~344 (2003)
- V. P. Chakka, "Indexing Large Trajectory Data Sets With SETI", Proc ofthe 1st Biennial Conference on Innovative Data Systems Research (2003)
- S. Saltenis, "Indexing the Positions of Continuously Moving Objects", Proc of the ACM International Conference on Management of Data, pp.331~342 (2000)
- S. Prabhakar, "Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects", IEEE Transactions on Computers, pp.1124~1140 (2002)
- Y. Tao, "The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries", Proc of the 29th International Conference on Very Large Data Bases, pp.790~801 (2003)
- H. Zhu, "Trajectory Queries and Octagons in Moving Object Databases", Proc of the ACM International Conference on Information and Knowledge Management, pp.413~421 (2002)