Spatio-temporal databases deal with data whose geometry changes over time. There are many real-life applications that create such data, including intelligent traffic systems and multimedia applications. This thesis presents an adaptive indexing technique for timestamp queries and interval queries using query workloads, and an efficient and scalable approach to nearest neighbor queries and continuous nearest neighbor queries in the presence of a road network.
Many spatio-temporal access methods, such as the HR-tree, the 3DR-tree, and the MV3R-tree, have been proposed for timestamp and interval queries. However, these access methods have the following problems: the poor performance of the 3DR-tree for timestamp queries, the huge size and the poor performance of the HR-tree for interval queries, and the large size and the high update cost of the MV3R-tree. We address these problems by proposing an adaptive partitioning technique called the Adaptive Partitioned R-tree (APR-tree) using workloads which consist of timestamp and interval queries. The APR-tree adaptively partitions the time domain using query workloads. Since the time domain of the APR-tree is automatically fitted to query workloads, the APR-tree is superior to the other access methods for various query workloads. The size of the APR-tree is on average 1.3 times larger than that of the 3DR-tree which has the smallest size. The average update cost of the APR-tree is similar to that of the 3DR-tree, which also has the smallest update cost.
A continuous search in a road network retrieves the objects which satisfy a query condition at any point on a path. For example, return the three nearest restaurants from all locations on my route from point s to point e. We deal with NN queries as well as continuous NN queries in spatio-temporal databases. The performance of existing approaches based on the network distance such as the shortest path length depends largely on the density of objects of interest. To overcome this problem, we propose UNICONS (a unique continuous search algorithm) for NN queries and CNN queries performed on a network. We incorporate the use of precomputed NN lists into Dijkstra\'s algorithm for NN queries. A mathematical rationale is employed to produce the final results of CNN queries. Experimental results for real-life datasets of various sizes show that UNICONS outperforms its competitors by up to 3.5 times for NN queries and 5 times for CNN queries depending on the density of objects and the number of NNs required.
시공간 데이타베이스는 시간에 따라 공간 정보가 바뀌는 데이터를 다룬다. 실생활에서 그러한 데이타를 생성하는 많은 응용 프로그램이 존재한다. 예를 들어, 지능형 교통 시스템과 멀티미디어 응용 프로그램이 이에 해당된다. 본 논문은 타임스탬프 질의와 인터벌 질의를 위한 적응적 색인 기법과 도로상에서 최근접 질의와 연속적 최근접 질의를 위한 효율적인 접근 방법을 제시한다.
타임스탬프 질의와 인터벌 질의들을 위하여 많은 시공간 데이터베이스 색인 기법들(예: HR-tree, 3DR-tree, MV3R-tree)이 제안되었다. 그러나, 이러한 색인 기법들은 다음과 같은 문제점들을 가지고 있다. 3DR-tree는 타임스탬프 질의에 대해서는 성능이 좋지 않다. HR-tree는 색인의 크기가 크고, 인터벌 질의에 대해서는 성능이 좋지 않다. MV3R-tree는 색인의 크기가 크고, 색인의 변경 비용이 크다. 본 논문에서는 타임스탬프 질의와 인터벌 질의로 구성된 질의 워크로드를 이용한 APR-tree (Adaptive Partitioned R-tree)를 제안한다. APR-tree는 질의 워크로드 정보를 이용하여 시간 도메인을 동적으로 분할한다. APR-tree의 시간 도메인은 자동적으로 질의 워크로드에 맞게 분할되기 때문에, APR-tree는 다양한 질의 워크로드에 대하여 다른 색인 기법들보다 우수한 성능을 보여준다. APR-tree의 크기는 가장 작은 색인 크기와 변경 비용을 나타내는 3DR-tree보다 평균적으로 1.3배 정도 크다.
도로위에서 연속적인 검색 질의는 주어진 경로상의 임의의 지점에서 질의 조건을 만족하는 객체들을 검색하는 것이다. 예를 들어, 점 s에서 점 e까지의 이동 경로상의 임의의 점에서 가까운 3개의 식당을 찾아달라는 사용자 질의가 존재할 수 있다. 도로상에서 최근접 질의와 연속적인 최근접 질의를 함께 다룬다. 최단 경로 거리와 같은 네트워크 거리를 이용하는 기존 방법들의 성능은 객체의 밀도에 따라 크게 영향을 받는다. 이 문제를 해결하기 위해서, UNICONS라는 최근접 질의와 연속적 최근접 질의를 위한 알고리즘을 제안한다. 미리 계산된 최근접 정보들은 Dijkstra의 알고리즘과 통합되어 이용된다. 연속된 최근접 질의의 최종 결과를 얻기 위하여 수학적인 접근법이 이용된다. 실제 데이타를 이용한 실험 결과는 객체들의 밀도나 요구되는 최근접 질의 조건에 따라 UNICONS가 비교 대상들보다 최근접 질의와 연속적 최근접 질의에 대하여 각각 최고 3.5배, 5배씩 개선된 결과를 보여준다.
