Research On Nearest Neighbors Query Based On Voronoi Diagrams And Reasoning With Direction Relation

Spatial query and reasoning as the basic functions of spatial database system have received a lot of attention. In this paper, we pay attention to the hot issues in spatial query and reasoning and mainly focus our efforts on nearest neighbors query, reverse nearest neighbors query and reasoning with direction relation.Nearest Neighbor (NN) and Continous Nearest Neighbor (CNN) query are two fundamental problems in the field of spatial databases. These types of queries are widely used in Geographic Information Systems, Pattern Recognition, Decision Support System et al.. All the existed methods achieve NN and CNN query processing by traversing R-tree. As is known to all, these methods suffer from the drawbacks of unnecessary traversals due to the fact that there are overlapping rectangles in intermediate nodes of R- tree and the performance of them deteriorates rapidly as the overlap between minimum bounding rectangles in the directory of R-tree increases.This paper devised an index VR-tree in which the voronoi diagrams of data set is embeded. This paper proposed an algorithm for nearest neighbor query in which VR-tree is employed; then proposed an algorithm for k nearest neighbors query which sharply lowered the cost by means of the properties of Voronoi diagrams to reduce search space; then, proposed a method using Voronoi diagrams and VR-tree to continuous nearest neighbor query; finally, proposed a method which dynamically constructs partial Voronoi diagrams for CNN query.This paper proposed an algorithm for reverse nearest neighbors query based on Delaunay triangulation which takes inquiry point as a generater of Delaunay triangulation and emploies the relationship between generater and adjacencies of generater. This algorithm only needs to search reverse nearest neighbors in adjacent generaters of query point which is no more six on everage. This algorithm based on Delaunay tree is not only efficient to resolve RNN inquiry but also more efficient to resolve RNN query when a point is added or deleted.Reasoning with direction relation which is an important branch of qualitative spatial reasoning is a hot issue in the field of spatial databases. Now, researches on direction relation on three dimension are rare and the precision of representation and reasoning is low, for which, we conduct the following researches.This paper proposes an algorithm to reason about the inverse of basic cardinal direction relation between regions themselves. The results of both analyzing in theory and verifying through comparing the result of the algorithm with the actual situation for each of basic cardinal direction relations demonstrate that the algorithm is correct and complete.This paper proposes a model for direction in three dimensions, which is an extension of direction relationship matrix model on the plane and offers qualitative direction relationship composition methods in this mode, exemplifies the correctness of the composition methods.This paper originally proposes the concept of qualitative Cartesian rectangular coordinate and then a model based on this concept is provided for position relation between regions . This model well reflects the shape of object and the spatial configuration between regions, excellently represents position relation between regions and effectively integrates direction with distance by means of qualitative Cartesian rectangular coordinates in essence which forms a unified model used to represent and reason. An algorithm which is proved to be correct in theory is proposed to improve the precision of reasoning with cardinal direction relation. The results of both analyzing in theory and verifying through large amounts of examples demonstrate that the algorithm indeed improves the precision of reasoning.