이동체를 위한 R-트리 기반 색인에서의 궤적 클러스터링 정책
Policies of Trajectory Clstering in Index based on R-trees for Moving Objects
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
이동체 데이터베이스를 위한 과거 궤적 색인으로 R-tree계열이 많이 사용되었다. 그러나 R-tree계열의 색인은 공간 근접성만을 고려하였기 때문에 동일 궤적을 검색을 할 때 많은 노드 접근이 필요하다. 즉 기존의 이동체 색인들은 공간 근접성과 궤적 연결성이 서로 상반된 특징을 가지므로 함께 고려하지 못했다. 이동체 색인에서 영역 질의의 성능개선을 위해서는 노드 간의 심한 중복과 사장 공간(Dead space)을 줄여야 하고, 궤적 질의의 성능 개선을 위해서는 이동체의 궤적 보존이 이루어져야 한다. 이와 같은 요구 조건을 만족하기 위해, 이 논문에서는 R-tree 기반의 색인 구조에서 궤적 클러스터링 정책을 제안한다. 노드 분할 정책에서는 궤적 클러스터링을 위해서 동일 궤적을 그룹화해서 분할하는 공간 축 분할 정책과 공간 활용도를 높이는 시간 축 분할 정책을 제안한다. 또한 비단말 노드의 연결 정보를 저장하여 개선된 복합 질의 알고리즘을 제안하였다. 이 논문에서는 제안한 R-tree기반 색인 구조의 구현 및 성능 평가를 통해서 검색성능이 우수함을 보였다.
Abstract
The R-trees are usually used for an index of trajectories in moving-objects databases. However, they need to access a number of nodes to trace same trajectories because of considering only a spatial proximity. Overlaps and dead spaces should be minimized to enhance the performance of range queries in moving-objects indexes. Trajectories of moving-objects should be preserved to enhance the performance of the trajectory queries. In this paper, we propose the TP3DR-tree(Trajectory Preserved 3DR-tree) using clusters of trajectories for range and trajectory queries. The TP3DR-tree uses two split policies: one is a spatial splitting that splits the same trajectory by clustering and the other is a time splitting that increases space utilization. In addition, we use connecting information in non-leaf nodes to enhance the performance of combined-queries. Our experiments show that the new index outperforms the others in processing queries on various datasets.
참고문헌 (16)
- Y. Theodoridis, "Spatio-temporal indexing for large multimedia applications", pp.441~448 (1996)
- D. Pfoser, "Novel approaches in query processing for moving objects", pp.395~406 (2000)
- Y. Theodoridis, "On the generation of spatiotemporal datasets", pp.147~164 (1999)
- B. Jun, "Dynamic splitting policies of the adaptive 3DR-tree for indexing continuously moving objects" (2003)
- B.-U. Pagel, "Towards an analysis of range query performance in spatial data structures", pp.214-221, pp.1993~
- D. Pfoser, "Indexing trajectories in query processing for moving objects", ch-99-3 (1999)
- N. Beckmann, "The R*-tree:An efficient and robust access method for points and rectangles", pp.332~331 (1990)
- D. A. Keim, "An index structure for high-dimensional data", pp.28~39 (1996)
- A. Guttman, "R-trees:A dynamic index structure for spatial searching", pp.47~54 (1984)
- M. Hadjieleftheriou, "Efficient indexing of spatiotemporal objects", pp.251-268, pp.2002~
- M. A. Nascimento, "Access structure for moving points" (1998)
- M. A. Nascimento, "Evaluation of access structures for discretely moving points", pp.171~188 (1999)
- D. Pfoser, "Indexing the trajectories of moving objects", 25(2), pp.3 2002~9
- T. K. Sellis, "A dynamic index for multi-dimensional objects", pp.507~518 (1987)
- A. P. Sistla, "Modeling and querying moving objects", pp.422-432, pp.1997~
- Y. Theodoridis, "Specifications for efficient indexing in spatiotemporal databases", pp.123~132 (1998)