Research On Complex Query Processing In Spatiotemporal Databases

With the rapid development of the Internet and wide use of sensors and GPS service, large amounts of spatial and spatiotemporal data have been and are continuously being collected. Therefore, techniques of managing spatiotemporal data have become a attractive filed in re-search. A spatiotemporal database embodies spatial, temporal, and spatiotemporal database concepts. Lots of previous works of managing data in a spatiotemporal database focus on data modeling, index constructing and query processing.However existing works no longer suffice new query types on new data types in new appli-cations. For example, in many applications, such as online dating or job hunting websites, users often need to search for potential matches based on the requirements or preferences imposed by both sides. This kind of requirements cannot be solved by common types of queries, such as range queries or nearest neighbor queries. In addition, due to various reasons, uncertainty is inherent in spatial and spatiotemporal data obtained in many applications. Index structures and query algorithms proposed for certain data both fail to due with data with uncertainty in terms of the correctness in answers and the efficiency in query processing. Furthermore, many real data easily have dozens of attributes, so the need for data managing techniques that work well in high dimensional spaces is compelling.To tackle the main issues in query processing for new query types on new data types, this thesis focuses on the following key techniques:matching query processing on certain spa-tial data, range query and similarity query processing on uncertain high-dimensional data and similarity search on uncertain spatiotemporal trajectory data. The main contributions are sum-marized as follows:(1) The thesis gives an in-depth study of previous index constructing and query processing techniques on certain spatial data, uncertain spatial data, certain spatiotemporal data and uncertain spatiotemporal data. Then the thesis analyzes the advantages and drawbacks of these exiting techniques. (2) According to the requirements on many web applications, we propose matching queries on spatial data. To process matching queries efficiently, we propose a general processing framework, which can efficiently process various forms of matching queries. Moreover, we elaborate the detailed processing algorithms for three particular forms of matching queries to illustrate the applicability of this framework. An extensive experimental study with both synthetic and real datasets indicates that, for various matching queries, our techniques can dramatically improve the query performance, especially when the dimen-sionality is high.(3) We define two most popular query types of uncertain spatial data, probabilistic range queries and probabilistic similarity queries. We propose a technique called DuoWave for indexing uncertain multidimensional objects under a commonly used data model. We also propose novel, efficient algorithms to process probabilistic range queries and probabilistic similarity queries. Extensive experiments show that DuoWave significantly outperforms state-of-the-art techniques, especially in high-dimensional space. Moreover, DuoWave can also be exploited for a number of other query types on uncertain data.(4) We introduce a novel and adaptive notion to measure the dissimilarity between two un-certain trajectories. Based on this notion, we define top-k similarity query (KSQ) on uncertain trajectories. A KSQ returns the k trajectories that are most similar to a given trajectory. To process such queries efficiently, we design UTgrid for indexing uncertain trajectories, and develop query processing algorithms that make use of UTgrid for ef-fective pruning. We conduct an extensive experimental study on both synthetic and real datasets. The results indicate that UTgrid is an effective indexing method for similarity search on uncertain trajectories. Our query processing using UTgrid dramatically im-proves the query performance and scales well in terms of query time and I/O.