이동객체 환경에서 이웃 노드 정보를 활용한 2계층 공간 색인 구조 = Two Layer Spatical Index Structure using Neighbor Node Information in Moving Object Environments

국문 초록 (Abstract)

최근 위치 인식 기술과 휴대 기기의 발달로 인해 이동 객체를 기반으로 하는 위치 기반 서비스에 대한 관심이 점점 증가하고 있다. 본 논문에서는 이동객체 환경에서 빠른 질의 처리를 지원하는 공간 색인 구조를 제안한다. 제안하는 공간 색인 구조는 kd-tree의 공간 분할 개념을 이용한다. 그리고 질의 처리 시 상위 노드의 탐색 비용을 감소시키기 위해서, B+-tree처럼 단말 노드에서 이웃 노드들의 링크를 유지한다. 또한 트리 구조를 이용하지 않고 직접 접근을 지원하는 그리드 구조를 이용하여 질의 처리시 단말 노드에 접근하기 위한 트리 탐색 비용을 절감하였다. 마지막으로 성능 평가를 통해 제안하는 색인 구조의 우수성을 보여준다.

다국어 초록 (Multilingual Abstract)

With the development of location aware techniques and mobile devices, the interests of location based services (LBS) have been highly increased. In this paper, we propose a spatial index structure that provides efficient query processing for the moving objects. The proposed index structure is based on a grid structure that provides direct accesses to data pages. It also uses the splitting policy of the kd-tree to make a leaf node. In addition, each leaf node maintains the links to neighbor leaf nodes like B+-tree to avoid unnecessary parent node accesses to search a neighbor node. It is shown through performance evaluation that the proposed index structure outperforms the existing schemes.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 제안하는 색인 구조
• 4. 성능 평가
• 5. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

1 S. Chen, "ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects" 29-42, 2008

2 A. Gutmann, "R-trees: A dynamic index structure for spatial searching" 47-57, 1984

3 S. Saltenis, "Indexing the Positions of Continuously Moving Objects" 331-342, 2000

4 Y. Tao, "Continuous Nearest Neighbor Search" 287-298, 2002

5 Y. Park, "An Index Structure for Efficient k-NN Query Processing in Location Based Services" 20-22, 2009