A new K-NN query algorithm based on the symmetric virtual grid and dynamic circle

The effective implementation of the spatial K-NN query is a particularly concerned problem in geographic information system. In the previous K-NN query algorithms, the tree index will use measurement distance and pruning strategies to reduce the required search space, the grid index will divide the space region into the grid cells with a certain size, search the neighbor region of the queried object through the location relationship among the grid cells, based on the previous K-NN algorithm study, a new K-NN query algorithm based on the symmetric virtual grid and dynamic circle is proposed in this paper, the algorithm will mainly union the data objects whose grid cells are symmetrical with the grid cell which the queried object is in and the queried object, and form multiple virtual grids, query in accordance with the order form inside to outside. In the searching process, use the queried object as the center, the largest K-NN distance in the virtual grid as the radius to make the dynamic circle so as to find the data objects to be searched first in the next virtual grid, the experiments show that the improved K-NN query algorithm can accurately and effectively find the neighbor objects meeting the conditions, and has a wide range of applications in practice.