Research On The Multi-Type Nearest Neighbor Query In Spatio-Temporal Database

Spatio-temporal database can be applied to storing and organizing every kind of spatial objects whose locations and forms are changing as time elapsed. The research on spatio-temporal database is paid more and more attention with the increasing requirements. As the important part of query processing techniques in spatio-temporal database, the nearest neighbor query has become a key and hot spot certainly. The concept of nearest neighbor query was first proposed in the theory of spatial database. Based on the unchanging meaning of nearest neighbor query, the object's motion status is extended to contain moving objects besides static objects in spatio-temporal database. And it makes the query processing become more challenging. Although many scientific researchers are engaged in the nearest neighbor query research in spatio-temporal database and have made remarkable achievements so far, there are still some disadvantages in the existing methods to nearest neighbor query and many unresolved problems in the new nearest neighbor queries with the in-depth study of spatio-temporal database and continuous developments of industrial techniques. The complex and diverse query requirements that spring up unceasingly in real life cannot be covered completely by what the researchers studied on nearest neighbor queries in spatio-temporal database. As a result, the research on nearest neighbor queries in spatio-temporal database still develops steadily and thus a further explore will be required.In view of the above-mentioned facts, the variant of nearest neighbor query in spatio-temporal database, that is, the multi-type nearest neighbor query is studied in this dissertation. It combines the multi-type nearest neighbor query with other nearest neighbor queries. The static multi-type nearest neighbor query is first to be considered, and then the problems in the condition of existing obstacles and moving object are studied deeply. It makes the multi-type nearest neighbor query more concrete and practical. The motive is to perfect the techniques of query processing in spatio-temporal database, and meet the query requirements of users which become more and more various and complex. The innovative contributions in this dissertation are summarized as follows:Firstly, the group nearest neighbor query problem is discussed. The conditions which group nearest neighbor should be satisfied are proposed, which attained by analysing the distribution characteristic of query points, the attributes of geometric figures that they form and the qualities of group nearest neighbor function. The theories that evaluate the group nearest neighbor are put forward by combinational using the conditions and the adjacent property of Voronoi diagrams. The VTree index grounded on Voronoi diagrams is brought forward, and the algorithm is presented which deals with group nearest neighbor query based on VTree index. The performance of the proposed algorithm is analyzed through the theoretical and experimental aspects. Experimental results show that the performance and stability of the proposed algorithm in the condition of non-collinear query points are better than that in the condition of collinear query points.Secondly, the concept of constrained multi-type nearest neighbor query is put forward. In the case of the constrained datasets ranges which are constructed by arbitrary simple polygons, the query algorithm based on the R-tree is proposed. Some characteristics, such as the minimal circumscribed rectangle of an ellipse can be figured out easily and the area which it contains is no better than the area which is covered with the same ellipse, and the pruning strategies achieved by a list structure are used in this algorithm. The analysis results in theory and experiments are shown and indicate that the proposed algorithm has better performance.Thirdly, the specific problem of multi-type nearest neighbor query, named optimal sequenced route query problem, is studied in the condition of existing obstacles. The problems of k completely different visible optimal sequenced route query and k obstructed globally different optimal sequenced route query are proposed. The approximate query algorithms which deal with the two query problems respectively are put forward by using the idea of nearest neighbor. The performance of these proposed algorithms is verified systematically in the experiments, and the results show that these proposed algorithms have better performance.Fourthly, the continuous nearest neighbors query for historical trajectories of moving objects is studied. The theory is presented by analyzing the characteristics such as the intersections of trajectories and the monotonicity of trajectory segments, and in view of the theory, a method for query continuous nearest neighbors directly is proposed for historical trajectories of moving objects. The kind of method makes it possible not to change the coordinates of moving objects. The results of experimental analysis and comparison are brought forward and show that the method proposed has better performace than the existing methods.Finally, the problem of continuous k optimal sequenced route query for moving objects is put forward which aims at the optimal sequenced route query problem in the condition of existing moving object. The static-global algorithm and the dynamic-local one are proposed to answer such queries on the moving-query and static-objects case. The performance of the proposed algorithms is evaluated experimentally, and the results show that the proposed algorithms can resolve this query problem preferably.The production develops and perfects the query processing techniques in spatio-temporal database valuably, and lays the foundation of the further advances on spatio-temporal database.