Research On Spatial Data Index Based On Nearest Neighbor Distance And Query Algorithms

With the advent of the era of big data information,how to deal with quantified spatial data has become a difficult problem.As a result,spatial database technology has emerged at the historic moment,and has been widely used in GIS,Geo-fence,decision support,and facility positioning.In addition,nearest neighbor query and reverse nearest neighbor query are the most important operations,and they are also the research focus of scholars in this field.The research on spatial data indexing algorithms in this paper mainly includes three parts: new spatial data index structure,reverse nearest neighbor query algorithm based on new index structure,and nearest neighbor query algorithm.Firstly,for the reverse nearest neighbor problem,a new spatial data index structure--MBDNN-tree(index tree based on the minimum bounding square and the distance of nearest neighbor)is proposed,by using the ordering relationship between the smallest surrounding square and the spatial data rectangle.The index structure uses the good properties of MBSD(minimum bounding square based on nearest neighbor distance)and various order relationships.When constructing the index structure,the MBSD corresponding to spatial data can be divided into different levels.Each level(node)contains MBSDs with relatively close spatial distance.To do so reduces the area of overlap between nodes and access to visit invalid paths when queries are processed to optimize its performance.On the basis of this,a new spatial data index structure--MBDNN-tree is given.And the generating and updating algorithms for MBDNN-tree are presented.Secondly,new query pruning rules are designed for reverse nearest neighbor query on MBDNN-tree,by taking the properties of the reverse nearest neighbor query and the characteristics of MBDNN-tree,and related reverse nearest neighbor query algorithm is given.The algorithm uses multiple order relationships to optimize the index structure,reducing the overlap between different nodes,thereby reducing invalid paths and access to invalid nodes,so as to improve the performance of reverse nearest neighbor query.Experiments and analysis show that the reversenearest neighbor query algorithm based on MBDNN-tree has much better query performance.Finally,a new nearest neighbor query algorithm on MBDNN-tree is proposed.This algorithm uses the different order relationships between nodes in each layer of the MBDNN-tree to speed up nearest neighbor query.During the query process,4different pruning strategies are used for prune off different nodes,and a large number of useless nodes are filtered out.The number of visited nodes is reduced,so the query process is shortened,and the query speed of the algorithm is accelerated.Experimental analysis shows that the nearest neighbor query algorithm has higher query efficiency than other algorithms.