一种快速搜索海量数据集K-近邻空间球算法

 提出了一种快速搜索海量数据集K-近邻的空间球搜索算法。将数据点集进行空间栅格划分,假想存在空间球,并以当前测点为球心,半径分别取测点到所在立方体栅格6面的距离。首先取半径最小的空间球,在与之发生干涉的栅格中进行K-近邻搜索,若满足所建立的搜索终止原则,则终止搜索;否则,取更大半径的空间球,重复上述过程。实验结果表明,所提出的算法可对海量数据集进行快速K-近邻搜索,较已有算法明显提高搜索速度。

A Spatial Sphere Algorithm for Searching K-Nearest Neighbors of Massive Scattered Points

A spatial sphere algorithm is proposed for searching K-Nearest Neighbors (K-NN) of one measured point in scattered point set.At first,the scattered points are divided into a set of uniform cells.Suppose there exist a series of spatial spheres with the same center being the current point,and the radii being the distances from the point to one of the six cells planes respectively.A sphere with the smallest radius is first taken to determine the cells that interfere spatially with the sphere.Then a K-NN search is carried out within the interfering grids until the searching termination condition is satisfied.Otherwise,the sphere with larger radius is taken,and above searching process is repeated.Experiments show that the algorithm is very fast to search K-NN of scattered points in comparison with existing algorithms.