海量空间数据点k近邻的快速搜索算法

Algorithm for Fast Searching of k-nearest Neighbors in Cloud Points

提出一种新的海量空间数据点k近邻的快速搜索算法.本算法综合考虑了空间数据的范围、数据点的总数、近邻点数目k以及数据点的密度,给出了一种新的估算子立方体边长的方法;采用空间分块策略,把数据空间划分成多个子立方体,子立方体的大小决定k近邻的搜索速度;最后记录每个子立方体所包含的数据点及每个点所属的子立方体编号,搜索测点的k近邻.大量数据的实验结果表明本算法可以大大提高在海量空间数据点中搜索测点k近邻的速度.

A new algorithm of fast searching k nearest neighbors in cloud data is presented in thepaper A method of estimating the size of sub-cube is introduced by considering the range of data set , the total numbers , the density of points and the numbers of nearest neighbors. Then the minimal box of the data set is divided into a set of subcubes and the searching speed is decided by the number of the sub-cubes. Finally, the points are assigned to the appropriate sub- cubes for searching k nearest neighbors of the testing point. Simulation experiments show that the searching speed of k nearest neighbors is improved.