A query optimizer requires selectivity estimation of a query to choose the most efficient access plan. However, an effective method of selectivity estimation for the future locations of moving objects has not yet been proposed. In spatial databases, existing methods for spatial selectivity estimation do not accurately estimate the selectivity of a query to moving objects, because they do not consider the future locations of moving objects, which change continuously as time passes.
In this thesis, we propose an effective method for spatio-temporal selectivity estimation to solve this problem. We present analytical formulas which accurately calculate the selectivity of a spatio-temporal query as a function of spatio-temporal information. Our analytical formulas can be basically used by various cost models for moving objects.
Recently, the TPR-tree has been proposed to support spatio-temporal queries for moving objects. And, various methods using the TPR-tree have been intensively studied. However, although the TPR-tree is one of the most popular access methods in spatio-temporal databases, any cost model for the TPR-tree has not yet been proposed. As a result, a query optimizer may choose an inefficient plan for a spatio-temporal query. Existing cost models for the spatial index such as the R-tree do not accurately estimate the number of disk(or page) accesses for spatio-temporal queries using the TPR-tree, because they only handle the spatial locations of objects at the current time. In this thesis, we propose a cost model of the TPR-tree for moving objects for the first time.
To conduct experiments in a realistic environment, we generate synthetic moving objects by using real-life spatial data with a reasonable skew distribution. In the experiments, the proposed methods provide accurate estimation results over various queries with different spatial area sizes and time interval lengths.
To our knowledge, the proposed spatio-temporal selectivity estimation method is the first work specifically addressing the selectivity estimation method for moving objects. So, we compared our proposed method with an existing spatial selectivity estimation method. It was observed that our proposed method accurately estimated the selectivity of a query to moving objects, compared with the existing spatial selectivity estimation method. Also, experimental results showed that our cost model accurately estimated the number of disk accesses for spatio-temporal queries using the TPR-tree.
질의 최적화기는 가장 효율적인 액세스 플랜을 선택하기 위해서 질의의 선택률 추정을 요구한다. 그러나, 움직이는 객체의 미래 위치를 위한 선택률 추정의 효과적인 방법은 아직까지 제시되지 않았다. 공간 데이타베이스에서, 공간 질의의 선택률 추정을 위한 존재하는 방법들은 움직이는 객체들의 미래 위치를 고려하지 않기 때문에, 움직이는 객체에 대한 시공간 질의의 선택률을 정확하게 예측하지 못한다.
이 논문에서는 이러한 문제를 해결하기 위한 시공간 선택률 추정을 위한 효과적인 방법을 제안한다. 시공간 질의의 선택률을 정확하게 예측하는 시공간 정보의 함수로써 분석적인 수식들을 제시한다. 이러한 분석적인 수식들은 움직이는 객체에 대한 다앙한 비용 모델들에 의해 기본적으로 사용될 수 있는 장점을 제공한다.
최근에, 시공간 질의를 효율적으로 지원하기 위한 TPR-tree가 제안되었으며, 이러한 TPR-tree는 다양한 질의 처리에 사용되었다. TPR-tree의 비용 모델은 질의를 위한 다양한 액세스 플랜의 비용들을 계산하기 위해서 질의 최적화기에 의해 필요함에도 불구하고, 아직까지 시공간 질의를 위한 디스크(또는 페이지) 액세스 수를 예측하는 효과적인 방법이 제시되지 않았다. R-tree와 같은 공간 색인에 대한 존재하는 비용 모델들은 움직이는 객체의 미래 위치를 고려하지 않기 때문에, TPR-tree를 사용한 시공간 질의를 위한 디스크 액세스 수를 정확하게 예측하지 못한다. 이 논문에서는 움직이는 객체를 위한 TPR-tree의 비용 모델을 처음으로 제안한다.
현실적인 실험 환경을 위해서, 적당히 편중된 분포를 나타내는 실 세계 공간 데이타를 사용하여 인위적으로 움직이는 객체를 생성하였다. 실험에서, 제안된 방법들은 다른 공간 영역 크기와 시간 간격 길이를 가진 다양한 시공간 질의에서 정확한 예측 결과를 보였다.
이 논문에서 제안된 시공간 선택률 추정 연구는 움직이는 객체에 대한 선택율 추정을 알리는 첫 번째 연구이다. 그래서, 존재하는 공간 선택율 추정 방법과 제안된 방법을 비교하였다. 존재하는 공간 선택률 추정 방법과 비교할 때, 이 논문의 제안된 방법은 움직이는 객체에 대한 질의의 선택률을 정확하게 예측하였다. 또한, 제안된 TPR-tree의 비용 모델이 시공간 질의를 위한 디스크 액세스 수를 정확하게 예측하는 실험 결과를 보였다.
