Reverse K Nearest Neighbor Query Based On Voronoi Diagram In Spatial Databases

With a wide range of applications for spatial database in the practical application fields,the research on nearest neighbor queries and their variants in spatial databases has become a hot issue.The nearest neighbor query has been unable to meet the wide application requirement,so the data environment of the nearest neighbor query become obstacle space and the data object become line segment.As an important special query type,reverse k nearest neighbor query has important research value.Since the existing research does not involve the group reverse k nearest neighbor query in the obstacle space and line segment reverse k nearest neighbor query,in this paper,we focus on the research of the group reverse k nearest neighbor query in the obstacle space and the line segment reverse k nearest neighbor query by using the adjacency properties of Voronoi diagram.Firstly,In order to solve the problem that the existing research results can not effectively deal with the problem of group reverse k nearest neighbor query in obstructed space,the group reverse k nearest neighbor query method in obstructed space based on Voronoi diagram(OGRk NN)was put forward.According to the changes of obstacle set,the OGRk NN query in static obstacle environment(STA_OGRk NN)and the OGRk NN query in dynamic obstacle environment(DYN_OGRk NN)are given.The STA_OGRk NN query method uses pruning strategy in the pruning phase quickly narrow the search range and improve the query efficiency of the algorithm,in the refining stage effectively improves the accuracy of the algorithm.Then three DYN_OGRk NN query algorithms are given.Secondly,in view of the limitations of the existing reverse k nearest neighbor query based on the point object,the line segment Rk NN query method in spatial database based on Voronoi diagram(LRk NN)is proposed.The method finds line segments that take the query line segment as one of their k nearest neighbors.The LRk NN method is divided into two processes: pruning process and refining process.We use 5 pruning strategies to selecte candidates,and then get the accurate result set according to the definition.Pruning process can greatly improve the query speed.Refining process can greatly improve the accuracy of the algorithm.Finally,the LRk NN query is improved to apply to the dynamic update of the data set.The line reverse k nearest neighbor query method for dynamic update of data set(DYN_LRk NN method)is proposed.According to the uncertainty of the dynamic dataset,two DYN_LRk NN query algorithms are given.they are the LRk NN query algorithm under the condition of dynamically increasing line segments(DYN_ADD_LRk NN algorithm)and the LRk NN query algorithm under the condition of dynamically reducing line segments(DYN_DEL_LRk NN algorithm).The DYN_LRk NN query method is divided into two stages: processing dataset stage,judgment stage.Judgment stage can avoid redundant query,and thus improve the efficiency of query.Then DYN_LRk NN algorithm is given.