| 利用空间微分块与动态球策略的k近邻搜索算法研究 |
| |
| 引用本文： | 马娟,方源敏,赵文亮,冯瑜瑾.利用空间微分块与动态球策略的k近邻搜索算法研究[J].武汉大学学报(信息科学版),2011(3):358-362. |
| |
| 作者姓名： | 马娟 方源敏 赵文亮 冯瑜瑾 |
| |
| 作者单位： | 西南交通大学土木工程学院测量工程系;昆明冶金高等专科学校测绘学院;昆明理工大学国土资源工程学院;昆明理工大学教育技术与网络中心; |
| |
| 基金项目： | 云南省应用基础研究面上资助项目(2009CD102) |
| |
| 摘 要： | 提出了一种基于空间微分块与动态球判定策略的k近邻快速搜索算法。该算法以空间包围盒为基础,首先对空间进行微分块,将离散点分配到子空间;然后,以计算点为球心建立动态球,确定k近邻候选点。球半径可根据空间包围盒的大小、离散点数量和k近邻点数进行估算和优化。实验结果表明,该算法可快速完成k近邻搜索,运行稳定可靠。
|
| 关 键 词： | 离散数据 k近邻 空间微分块 动态球 |
Algorithm for Finding k-Nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere |
| |
| MA Juan, FANG Yuanmin ZHAO Wenliang FENG Yujin.Algorithm for Finding k-Nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere[J].Geomatics and Information Science of Wuhan University,2011(3):358-362. |
| |
| Authors: | MA Juan FANG Yuanmin ZHAO Wenliang FENG Yujin |
| |
| Institution: | MA Juan1,2 FANG Yuanmin3 ZHAO Wenliang2 FENG Yujin4 (1 Department of Surveying Engineering,Southwest Jiaotong University,111 Erhuan Road,Chengdu 610031,China) (2 Department of Surveying,Kunming Metallurgy College,388 Xuefu Road,Kunming 650033,China) (3 Department of Land Resource and Surveying Engineering,Kunming University of Science and Technology,68 Wenchang Road,Kunming 650093,China) (4 Educational Technology and Network Center,Kunming 650093... |
| |
| Abstract: | 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... |
| |
| Keywords: | scattered points k-nearest neighbors spatial sub-cubes dynamic sphere |
| 本文献已被 CNKI 等数据库收录！ |
|
