Algorithm for Finding k-Nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere

A new algorithm for finding k-nearest neighbors based on spatial sub-cubes and dynamic sphere is presented.At first,the min-max box of the dataset is divided into a set of uniform sub-cubes,every point is distributed in a sub-cube.Then the dynamic sphere is builded using the test point as the center of sphere in order to reduce the searching scope.The radius of sphere can be estimated and adjusted according to the volume of min-max box,the numbers of spatial points and the numbers of k-nearest neighbors.The experimental results show that the algorithm can find k-nearest neighbors fastly.