Research On Visible K-Nearest Neighbor And Reverse K-Nearest Neighbor Query In 3D Space

With the widespread use of smart transportation,3D virtual technology and spatial geographic information systems.Efficient data query processing technology has become the research focus of the majority of scholars.Visual query research is involved when there are obstacles in the query space.Existing visual nearest neighbor query algorithms are all studied in two-dimensional space.If they are directly applied to visual query research in three-dimensional space,query results will be wrong.In response to this problem,this paper gives the visual k-nearest neighbor query algorithm based on range-key points and the visual anti-k-nearest neighbor query algorithm based on range query in three-dimensional space.The research content is as follows:First,the objects in the three-dimensional space are all cubes that are perpendicular to the ground and have random rotation angles.Due to the different directions of the spatial objects,they lack a unified projection plane.Point theorem,and a visual k nearest neighbor query algorithm based on range-key points(Rkpt-Vk NN)is proposed.This algorithm firstly judges between the target object and the obstacle object If there is a key point,use the key point theorem to determine whether the target object is obscured by the obstacle object to obtain the candidate set;finally,the candidate set is purified according to the projection angle refining algorithm,which improves the query efficiency.Secondly,the Visible Reverse k nearest neighbor query(R-VRk NN algorithm)of the three-dimensional obstacle spatial range query is proposed.The algorithm first performs a completely visible k nearest neighbor query on the query point q,and takes the furthest distance of the kth fully visible object as the query area,and obtains all object sets within the range,and then performs anti-k nearest neighbor query processing on the object set To obtain the candidate set of anti-k nearest neighbors that may become query points.Finally,the candidate set is further processed through a refinement algorithm to obtain a result set,which effectively solves the problem of visual anti-k nearest neighbor query in three-dimensional space.Finally,the experimental comparison and analysis of the above-mentioned algorithms are carried out respectively.The experimental comparison is compared and analyzed in terms of data set size,k value,pruning time,and pruning ratio.The comparison results show that the algorithms proposed in this paper have efficient query performance.