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

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

作　　者：卫炜[1] 张丽艳[1] 周来水[1] 

机构地区：[1]南京航空航天大学CAD/CAM工程研究中心,江苏南京210016

出　　处：《航空学报》2006年第5期944-948,共5页Acta Aeronautica et Astronautica Sinica

基　　金：国家自然科学基金(50475041);霍英东教育基金会高校青年教师基金(91053)

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

关 键 词：K-近邻 海量数据 逆向工程 空间划分 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]