Recently, along with the development of wireless computing and GPS technologies, which can support a real-time tracking of moving objects, many applications using the moving object data have been developed. These types of applications include vehicle ...
Recently, along with the development of wireless computing and GPS technologies, which can support a real-time tracking of moving objects, many applications using the moving object data have been developed. These types of applications include vehicle tracking, digital battlefields, airplane traffic management systems, as well as location-based services. Mobile data management systems efficiently supporting such kinds of application services should be able to manage the moving objects that continuously change their positions over time.
Selectivity estimation is one of the query optimization techniques. It is difficult for previous selectivity estimation techniques to apply the real-time position data of moving objects to a synopsis. Therefore, they result in much error when estimating selectivity for queries, because they are based on the extended spatial synopsis which does not consider the property of the moving objects. In order to reduce the estimation error, the existing techniques should often rebuild the synopsis. Consequently problem occurs, that is, the whole database should be read frequently.
In this dissertation, we propose a moving object histogram method based on quad tree to develop a selectivity estimation technique for moving object queries. We then analyze the performance of the proposed method through the implementation and evaluation of the proposed method. The contents of this dissertation are as follows.
First, we describe a location information model and the definition of moving objects in two dimensional space. And we define a moving object database that manages location information of moving object.
Second, we propose a new selectivity estimation method for moving object queries. The proposed method can reflect the location change of moving objects in the synopsis. In order to construct such a synopsis we use quad tree and hash table. Our method can reduce the variance of velocity within a bucket due to the consideration of moving objects’ velocities in the step of spatial partitioning while constructing quad tree. Our method also can reduce the overhead which the whole index should be scanned to use the index based synopsis, since the synopsis of our method maintains as hash table in memory. To reduce the spatial overhead occurring when buckets are assigned to a target node in the index, we adjust the number of buckets according to the height level of the index.
Third, in order to reduce the estimation time, we minimize the number of buckets for which is necessary for selectivity estimation through the bucket filtering based on dimensional transformation. We also suggest a selectivity estimation algorithm for current and future queries.
Finally, we analyze the performance of the proposed method comparing with the existing methods via various performance studies. We will show that the proposed method can reflect the location change of moving objects over time in the synopsis better than the existing methods through the experimental results.
In summary, a new selectivity estimation method for current and future queries on moving objects is introduced in this dissertation. The proposed method has better performance than the existing methods since the location change of moving objects over time in the synopsis is reflected. Our method can manage and process queries on moving objects. Hence, it is able to be used in various location management systems such as vehicle location tracking systems, location based services, telematics services, emergency rescue service, etc in which the location information of moving objects changes over time.