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