利用空间微分块与动态球策略的k近邻搜索算法研究

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

提出了一种基于空间微分块与动态球判定策略的k近邻快速搜索算法。该算法以空间包围盒为基础,首先对空间进行微分块,将离散点分配到子空间;然后,以计算点为球心建立动态球,确定k近邻候选点。球半径可根据空间包围盒的大小、离散点数量和k近邻点数进行估算和优化。实验结果表明,该算法可快速完成k近邻搜索,运行稳定可靠。

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.