Research On Spatial Join And Variants Of Nearest Neighbor Query

With a wide range of applications for spatial database in GeographicInformation Systems(GIS), satellite image data processing systems, Computer-Aided Design and Manufacturing(CAD/CAM), and multimedia systems, spatialquery as the core problem of spatial database has become the research focus. Theefficiency of spatial query is an important indicator to measure the performanceof spatial database. The urgent requirements have been put on various spatialqueries in many practical applications. Spatial query performance is critical tothe success of these applications. Spatial join and nearest neighbor query areimportant queries of spatial queries. Research on new algorithms to improve theefficiency of these two queries is important for spatial queries. In this paper,spatial join and nearest neighbor variants query are studied, the main work can besummarized as the following five points:Firstly, the problem of spatial join query within the constrained range isstudied, and the concept of constrained spatial join query is put forward. Thecharacteristic of this query is analyzed. Two direct approachs and constrainedspatial join algorithm based on R-tree are given.By using of the goodcharacteristics of the hybrid spatial index structure QR-tree, the constrainedspatial join algorithm based on QR-tree is proposed. The method can not onlyavoid R-tree node duplication, but also overcome the large storage costs ofquadtree and solve the expensive cost problem for spatial join query. Query costof the algorithm is analyzed and compared. Theory and experiment prove that thealgorithm has high search efficiency.Secondly, the problem of reverse nearest neighbor query in obstacleenvironments is studied. A new variant of the reverse nearest neighbor querybased on obstructed distances is put forward, that is, obstructed reverse nearestneighbor query. Given an obstacle set, a data set, and a query point, obstructedreverse nearest neighbor query finds out the points in data set which take the query point as obstructed nearest neighbor. The filter and refinement two-stepalgorithm for obstructed reverse nearest neighbor query is raised. Experimentsprove that the proposed algorithm has high efficiency.Thirdly, the problem of group nearest neighbor query in obstacleenvironments is studied. A new variant of the group nearest neighbor query basedon obstructed distances is put forward, that is, group obstacle nearest neighborquery. It finds the point of data set with the smallest sum of obstructed distancesto all points in query data set. According to the positional relationship betweenthe point and MBR of query point set, the pruning region in variouscircumstances is constructed.By using of the pruning region,the obstacle set ispruned. And the obstructed distance calculation algorithm between the point andquery data set is put forward.The pruning rules of group obstacle nearestneighbor query are defined and group obstacle nearest neighbor query algorithmis given combined with the obstructed distance calculation algorithm.Experiments show that algorithms have higher query efficiency.Fourthly, the problem of continuous reverse nearest neighbor query indynamic environments is studied. Continuous monochromatic reverse nearestneighbor and continuous bichromatic reverse nearest neighbor are researched.Continuous reverse nearest neighbor query algorithms based on the Voronoidiagram are araised,and the relevant theorem and proof are given. According towhether change in the topology of the Voronoi diagram of moving points, it hastwo categories:change and no change.Corresponding solutions are given in eachcategory. A new variant of continuous reverse nearest neighbor query in obstacleenvironments is put forward, that is, continuous visible reverse nearest neighborquery. That finds out the points in data set which take the query line segment asvisible nearest neighbor. Through the visibility judgment of query line segmentand the corresponding pruning rules continuous visible reverse nearest neighborquery algorithms is proposed and related theorems and proofs are given.Experiments show that algorithms have higher query efficiency.Fifthly, the problem of spatial queries based on plane line segment is studied.The line segment closest pair query is proposed. That finds the line segment pairwhich have the shortest distance among all the pairs of two line segment sets.The line segment closest pair query algorithm based on Voronoi diagram is put forward. The Voronoi diagram of two line segment sets is construstedrespectively in this method. By making use of the good properties the result isfinded. The line segment reverse nearest neighbor query is researched. The linesegment reverse nearest neighbor query algorithm based on Voronoi diagram isproposed. According to whether two line segments are intersected,it has twocategories:intersected and no intersected. Corresponding solutions are given ineach category. Experiments demonstrate the proposed algorithms have high queryefficiency.