Research On Key Techniques Of Query Processing In Spatio-Temporal Databases

Advances in mobile computing, wireless communication, and positioning technologies have made it possible to store and manage a variety of spatial and spatiotemporal objects in practice. Many applications (e.g., geographical information systems, navigation systems, traffic control, weather forecast, digital battlefield, mobile e-commerce, etc.) call for searching such data objects efficiently. However, the great capacity and complexity of spatial and spatiotemporal data make conventional database query processing techniques no longer well suited, and require exploiting new query processing approaches. Therefore, how to provide all kinds of efficient query processing techniques for spatial and spatiotemporal objects is one of research hotspots in the area of spatio-temporal databases currently.The query efficiency is an important benchmark of the performance of spatio-temporal databases. Although numerous researchers have been effort on this area and obtained a number of valuable results, there is a gap for satisfying various query requirements of the users as well as the increasingly new query requirements. Furthermore, there are little domestic institutions which have engaged in investigating this area. There also exists a gap, comparing oversea research level in the area. Thus, research on query processing techniques in spatio-temporal databases has important academic value and extensive applications.Motivated by this, this dissertation studies the key techniques of query processing in spatio-temporal databases from following two aspects: (i) How to deal with various queries for spatial objects efficiently. In this aspect, the dissertation mainly focuses on parallel nearest neighbor search, parallel skyline query, branch-and-bound skyline query, and mutual (i.e., symmetric) nearest neighbor (MNN) retrieval, (ii) How to efficiently handle various queries over historical moving object trajectories. In this aspect, the dissertation mainly concentrates on k (≥1) nearest neighbor (ANN) search, historical continuous ANN (HCkNN) search, constrained kNN (CkNN) search, historical continuous CkNN (HCCkNN) search, MNN search, and historical continuous MNN (HCMNN) search.To sum up, our key contributions in this dissertation are as follows:1. Propose firstly best-first based parallel ANN query algorithms in multi-disk setting. The performance of the proposed algorithms outperforms the existing ones significantly in terms of efficiency and scalability.2. Present firstly parallel skyline query processing methods in multi-disk environment. The efficiency and scalability of these proposed algorithms are evaluated by extensive experiments. 3. Propose a memory-optimal branch-and-bound algorithm for skyline queries. In particular, the algorithm not only has optimal I/O cost (i.e., the number of node accesses) and low CPU overhead, but also minimizes storage space. Moreover, its performance exceeds the best congeneric algorithm so far.4. Research on the problem of the kNN and HCkNN query over historical moving object trajectories. Based on the best-first retrieval paradigm, this dissertation proposes kNN and HCkNN query processing approaches with respect to stationary query points and moving query trajectories, respectively. The performance of these methods is better than the existing algorithms in terms of efficiency and scalability. In addition, the dissertation introduces a novel distance metric, develops several pruning heuristics, and devises update strategies for maintaining the k nearest lists which store the query results of the HCkNN search.5. Explore firstly the problem of the MNN query for spatial objects. Specifically, this dissertation formalizes the MNN retrieval and analyzes the problem characteristics of this query as well as proposes a series of MNN query processing algorithms and evaluates their performance through considerable experiments in both efficiency and scalability.6. Discuss firstly the problem of the CkNN and HCCkNN query on historical moving object trajectories. Specifically, this dissertation defines formally CkNN and HCCkNN queries over trajectory data, proposes several query processing algorithms for CkNN and HCCkNN queries with respect to static query points and moving query trajectories, respectively. Then, the performance of these proposed methods is verified systematically.7. Research firstly on the problem of the MNN and HCMNN query for historical trajectories of moving objects. In particular, this dissertation defines formally MNN and HCMNN queries over trajectory data, proposes MNN and HCMNN query processing approaches with respect to static query points and moving query trajectories respectively, and experimentally evaluates the performance of the presented methods.The work of this dissertation not only enriches the theory system of the area of spatio-temporal databases, but also speeds up utility process of spatio-temporal databases and facilitates the applications of spatio-temporal databases in real life.