위치 기반 질의 처리를 위한 궤적 보존 색인의 설계 및 구현 (Design and Implementation of Trajectory Preservation Indices for Location Based Query Processing)

서지정보

· 발행기관 : 한국공간정보시스템학회
· 수록지 정보 : 한국공간정보시스템학회 논문지 / 10권 / 3호 / 67 ~ 78페이지
· 저자명 : 임덕성, 홍봉희

초록

위치 기반 서비스(Location-Based Service)는 무선 통신에 기반 한 서비스로서 최근 그 중요성이
증대되고 있다. 차량, 선박과 같이 시간에 따라 위치를 변경하는 이동 객체(moving object)의 이동
경로는 궤적(trajectory)으로 표현된다. 이동 객체의 궤적 모니터링을 위한 데이터베이스에서는 이동
객체의 위치를 추적할 뿐만 아니라 이동 경로를 감시하기 위한 궤적 질의를 효율적으로 지원해야 하므
로 이동 객체의 궤적 정보를 효과적으로 관리하고, 빠른 검색을 제공하는 이동 객체 색인 방법이 필요
하다. 이 논문에서는 먼저 기존 궤적 색인 구조에서 사장 영역 문제를 정의한다. 궤적 색인의 사장 영
역은 궤적 보존 속성으로 인해 공간적 지역성을 고려되지 않기 때문에 발생한다. 이를 해결하기 위해 이
논문에서는 사장 영역 및 비단말 노드간의 중첩을 줄이기 위해 엔트리 재배치 기법을 제시하고, 제안된
색인과 기존 알고리즘을 사용하는 색인과의 성능비교를 통하여 제시한 색인의 우수성을 입증한다.

영어초록

With the rapid development of wireless communication and mobile equipment, many
applications for location-based services have been emerging. Moving objects such as
vehicles and ships change their positions over time. Moving objects have their moving path,
called the trajectory, because they move continuously. To monitor the trajectory of moving
objects in a large scale database system, an efficient indexing scheme to processed queries
related to trajectories is required.
In this paper, we focus on the issues of minimizing the dead space of index structures. The
Minimum Bounding Boxes (MBBs) of non-leaf nodes in trajectory-preserving indexing
schemes have large amounts of dead space since trajectory preservation is achieved at the
sacrifice of the spatial locality of trajectories. In this thesis, we propose entry relocating
techniques to reduce dead space and overlaps in non-leaf nodes. we present performance
studies that compare the proposed index schemes with the TB-tree and the R*-tree under a
varying set of spatio-temporal queries.

참고자료

· 없음