Research On Continuous Visible Nearest Neighbor Queries For Spatial Objects

The great capacity and complexity of spatial 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 spatial databases currently. People have proposed various types of spatial database query processing techniques with different spatial index structure, and most of them are based on the R-tree, such as Nearest Neighbor Query,Reverse Nearest Neighbor Query,Continuous Nearest Neighbor Queries and Closest Pair Query. However, these query algorithms are considered only for a situation in which spatial data include only the query object, which can not be applied to the reality situation in which large numbers of obstacles object exist in space.This dissertation analyses the two common query types - Continuous Nearest Neighbor Query and Visible Nearest Neighbor Query, and proposed the type of Continuous Visible Nearest Neighbor (CVNN) Query, a novel type of spatial database query. In the situation that both query object and obstacles object exist in space, CVNN can obtain all the visible nearest neighbors of a mobile object moving in its trajectory. This algorithm can be applied for the part of AI in the game and it can support the leadership's decision-making. In addition, the thesis also discussed the variations of CVNN (Trajectory Continuous Visible Nearest Neighbor and Constrained Continuous Visible Nearest Neighbor).To sum up, our key contributions in this dissertation are as follows:1) Firstly, this thesis analyses the characteristics of the problem and the similarities and differences between the CNN and CVNN. And then we identify and prove some properties that facilitate the development of efficient algorithms.2) The algorithm employs some pruning of heuristic to reduce the access of the intermediate nodes while traversing R-tree of query objects. In order to reduce the overall running time, we propose a technology to determine quickly the influence of an obstacle to the final results. Due to updating results step-by-step, the accuracy of results is proved.3) In order to make more extensive application of algorithms, we extend our methods to multiple nearest neighbors which obtain k(>1) visible nearest neighbors. Taking into account that the properties of the question may lead to tremendous nodes access, this thesis presents a approximate algorithm that solve the problem with few cost.4) Finally we extend the algorithm to T-CVNN and C-CVNN, expanding the application in different environments.