A New K-nearest Neighbor Query Algorithm based on Grid Hierarchical Division

摘要

The grid index is an important class of indexing technique in the spatial database. Grid index is widely used in the K -nearest neighbor algorithm, the algorithm proposed in this paper is based on the grid index, find the data objects intersecting with the given circle area or contained in the given circle area and cluster the grids which these data objects are in, the remaining grids will be used as a whole to wait the next cluster, when carry on K-nearest neighbor query every time, it only needs to first query the clustered grids, so it can avoid the complex distance calculation between the queried object and the eight grids around the queried object. Experiments show that the time spent on finding the K-nearest neighbor objects is greatly reduced when the selected circle radius is appropriate, the search efficiency of the algorithm is also significantly increased.