Rapid advances in wireless communication and positioning technologies enable new application areas such as the location-based services. Representative location-based applications in various areas include mobile e-commerce, traffic control and military C4I systems and eventually lead the pervasive computing environment. These services can be achieved by the spatiotemporal database technology that concerns about the time-varying geometric information. In mobile environments, the positions of moving objects are represented as coordinates at a certain time or trajectories. Hence those two classes of location information are needed to be treated appropriately by the requirements of applications. However, managing exact geometric location information is difficult due to the continual changes of moving objects with traditional databases.
Indexing is one of the major research issues in the spatiotemporal databases and traditional indexes focus on optimization of node accesses during index construction that do not refer on-line continuous updates. For efficient handling of frequent updates as well as the query performance, we investigate previous indexing approaches and evaluate their performances firstly. As a result, we propose the $B^{st}$-tree that is based on quad partitioning index structure and space filling curve for point moving objects and use constraint database approach to improve the efficiency of future spatiotemporal query performance.
Our method provides an indexing framework for future location queries based on space partitioning and the dual transformation. And the multi-version structure increase its size as time progresses. Hence the performance enhancement is achieved by our cost-based time-window management algorithm that determines the appropriate index reorganization probabilistically induced by query cost functions. This approach can be applied for the trajectory indexing specifically in a next generation mobile communication systems.
However, in some cases, only fast and approximate query answers are required. Although various types of histograms have been widely used in the past both for approximate query answering and selectivity estimation, most of them are not appropriate to future location-based queries. We present a method giving approximate answers for future location-based query predicates on demand by using spatiotemporal histograms that maintain the concise location information in the dual space. We use the concept of entropy and marginal distribution to estimate the frequency distribution of data that is required by query predicates. Our proposed method can provide fast query answering and efficiently reflect the updated information incrementally without scanning whole databases periodically and experimental results show the accuracy is improved.
최근의 이동 통신과 측위 기술의 급속한 발전은 위치 기반 서비스와 같은 새로운 응용 분야를 이끌고 있다. 대표적인 위치 기반 서비스는 무선 전자 상거래, 교통 관리 그리고 군사 목적의 지휘 통제 시스템을 포함하며, 궁극적으로 편재 컴퓨팅 환경의 기초를 제공한다. 시간에 따라 변화하는 공간 속성을 다루는 시공간 데이터베이스는 이러한 위치 기반 서비스를 제공하기 위한 기반 기술로 알려져 있다. 무선 통신 환경에서 이동 객체의 위치는 특정 시간의 좌표 또는 궤적으로 표현되며, 두가지 종류의 위치 정보는 응용 서비스 요구에 따라 적절히 다루어 질 수 있어야 한다. 그러나 정확한 위치 정보 관리는 이동 객체의 지속적인 위치 변화로 인하여 기존의 데이터베이스에서 다루기 어려운 문제이다.
색인은 시공간 데이터베이스의 주요 연구 분야이며, 전통적인 색인 연구는 지속적인 갱신을 고려하지 않고 노드 접근 횟수를 최적화하는데 촛점을 맞추고 있다. 본 논문에서는 이동 객체의 지속적인 갱신을 반영하고 효율적인 질의 처리를 지원할 수 있는 기존 색인에 대한 조사와 성능 평가를 실시하였다. 이에 대한 결과로서 사분 분할과 Space Filling Curve를 기반으로 하는 $B^{st}$-tree를 이동 객체 색인 구조로서 제시하고, Constraint 데이터베이스 모델을 적용하여 효율적인 시공간 미래 질의 처리를 지원할 수 있도록 하였다.
제시하는 색인 구조는 공간 분할과 쌍대 변환을 기반으로 미래 위치 질의를 위한 색인 프레임워크를 제공한다. 다중 버전 기반의 색인은 시간 경과에 따라 색인 크기가 지속적으로 증가하며, 제시한 색인의 성능은 질의 비용 함수로부터 확률적으로 유도된 비용 기반 관리 알고리즘을 이용하여 색인의 재구성을 적절히 수행함으로써 개선하였다. 제시한 기법은 특히 차세대 동적 관리 프로토콜을 사용하는 이동 통신 환경에서 적용이 용이하다.
또한 일부 응용 서비스에서는 정합 질의 보다 신속한 근사 질의를 요구하는 경우가 있으며, 기존의 연구에서는 질의 최적화 등을 위한 선택도 추정 방법으로 히스토그램이 가장 보편적으로 사용되는 방법이지만, 미래 위치 기반 질의에 대해서는 추정 방법이 복잡하거나 결과의 정확도가 저하됨으로써 직접 적용이 곤란해진다.
본 논문에서는 미래의 시공간 영역 질의 술어에 대하여 신속하게 히스토그램을 생성할 수 있도록 엔트로피와 한계 분포 방법을 이용한 시공간 히스토그램을 제시한다. 제시하는 방법은 쌍대 공간에서 구성된 궤적 정보를 히스토그램으로 요약함으로써 주기적으로 전체 데이터베이스를 검색하지 않고 질의가 요구하는 시간의 데이터 분포를 한계 분포로 생성하며, 동적 갱신을 점증적으로 지원함으로써 신속한 결과를 얻을 수 있고, 실험을 통하여 상대적으로 정확도가 우수함을 보인다.
