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

马娟; 方源敏; 赵文亮; 冯瑜瑾

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

马娟, 方源敏, 赵文亮, 冯瑜瑾

文章导航 > 武汉大学学报 ● 信息科学版 > 2011 > 36(3): 358-362

马娟, 方源敏, 赵文亮, 冯瑜瑾. 利用空间微分块与动态球策略的k近邻搜索算法研究[J]. 武汉大学学报 ● 信息科学版, 2011, 36(3): 358-362.

引用本文:

马娟, 方源敏, 赵文亮, 冯瑜瑾. 利用空间微分块与动态球策略的k近邻搜索算法研究[J]. 武汉大学学报 ● 信息科学版, 2011, 36(3): 358-362.

MA Juan, FANG Yuanmin, ZHAO Wenliang. Algorithm for Finding k-Nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 358-362.

Citation:

MA Juan, FANG Yuanmin, ZHAO Wenliang. Algorithm for Finding k-Nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 358-362.

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

¹西南交通大学土木工程学院测量工程系,成都市二环路北一段111号610031;²昆明冶金高等专科学校测绘学院,昆明市学府路388号,650033;²昆明理工大学国土资源工程学院,昆明市文昌路68号650093;⁴昆明理工大学教育技术与网络中心,昆明市文昌路68号650093

基金项目: 云南省应用基础研究面上资助项目(2009CD102)

详细信息

作者简介:
马娟,博士生,讲师,主要从事三维GIS理论及应用研究。

中图分类号: P208

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

¹ Department of Surveying Engineering,Southwest Jiaotong University,111 Erhuan Road,Chengdu 610031,China;² Department of Surveying,Kunming Metallurgy College,388 Xuefu Road,Kunming 650033,China;³ Department of Land Resource and Surveying Engineering,Kunming University of Science and Technology,68 Wenchang Road,Kunming 650093,China;⁴ Educational Technology and Network Center,Kunming University of Science and Technology,68 Wenchang Road,Kunming 650093,China

Funds: 云南省应用基础研究面上资助项目(2009CD102)

摘要: 提出了一种基于空间微分块与动态球判定策略的k近邻快速搜索算法。该算法以空间包围盒为基础,首先对空间进行微分块,将离散点分配到子空间;然后,以计算点为球心建立动态球,确定k近邻候选点。球半径可根据空间包围盒的大小、离散点数量和k近邻点数进行估算和优化。实验结果表明,该算法可快速完成k近邻搜索,运行稳定可靠。
- 离散数据 /
- k近邻 /
- 空间微分块 /
- 动态球
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 experimental results show that the algorithm can find k-nearest neighbors fastly.
- scattered points /
- k-nearest neighbors /
- spatial sub-cubes /
- dynamic sphere

[1]	余列冰, 向隆刚, 孙尚宇, 关雪峰, 吴华意. 面向分布式列式存储的轨迹大数据k近邻查询 . 武汉大学学报 ● 信息科学版, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
[2]	孙伟伟, 刘春, 李巍岳. 联合改进拉普拉斯特征映射和k_近邻分类器的高光谱影像分类 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1151-1156. doi: 10.13203/j .whu g is20130654
[3]	周新刚, 乐阳, 叶嘉安, 王海军, 仲腾. 动态数据空间分析的不确定性问题——以城市中心识别为例 . 武汉大学学报 ● 信息科学版, 2014, 39(6): 701-705. doi: 10.13203/j.whugis20140074
[4]	潘少明, 徐正全, 刘小俊. 空间数据访问规律的动态统计算法 . 武汉大学学报 ● 信息科学版, 2013, 38(6): 734-736.
[5]	周亚男, 骆剑承, 程熙, 沈占锋. 多特征融入的自适应遥感影像多尺度分割 . 武汉大学学报 ● 信息科学版, 2013, 38(1): 19-22.
[6]	周平, 唐新明, 张过. 多时相统计数据空间动态可视化模型研究 . 武汉大学学报 ● 信息科学版, 2012, 37(9): 1130-1133.
[7]	李忠民, 喻占武, 朱莉. 基于空间数据内容的动态负载均衡方法 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 622-625.
[8]	边馥苓, 万幼. k-邻近空间关系下的空间同位模式挖掘算法 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 331-334.
[9]	韩元利, 王海军, 夏文芳. 基于k阶数据场的城镇土地定级模型 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 370-373.
[10]	柳景斌, 王泽民, 王海军, 章红平. 利用球冠谐分析方法和GPS数据建立中国区域电离层TEC模型 . 武汉大学学报 ● 信息科学版, 2008, 33(8): 792-795.
[11]	肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.
[12]	林承达, 孟令奎, 彭溢. 无线GIS空间数据动态副本管理研究 . 武汉大学学报 ● 信息科学版, 2007, 32(3): 263-265.
[13]	韩元利, 胡鹏, 黄雪莲, 张立华. 基于k阶Voronoi多边形划分的k阶数据场拟合 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 353-357.
[14]	陈军, 李志林, 蒋捷, 朱庆. 多维动态GIS空间数据模型与方法的研究 . 武汉大学学报 ● 信息科学版, 2004, 29(10): 858-862.
[15]	李建成. 球外部空间的Neumann逆问题及逆Stokes公式 . 武汉大学学报 ● 信息科学版, 2003, 28(6): 655-657.
[16]	陈军, 蒋捷. 多维动态GIS的空间数据建模、处理与分析 . 武汉大学学报 ● 信息科学版, 2000, 25(3): 189-195.
[17]	刘丁酉, 胡新启. Banach空间中二阶微分包含的解 . 武汉大学学报 ● 信息科学版, 1997, 22(1): 87-89.
[18]	邓朝晖, 贾华. 矢量数据的一种分层动态组织方法 . 武汉大学学报 ● 信息科学版, 1995, 20(2): 118-122.
[19]	贾明海. 矿山开采变形观测的动态数据处理 . 武汉大学学报 ● 信息科学版, 1989, 14(2): 10-19.
[20]	徐因. 用近邻权法推估重力异常 . 武汉大学学报 ● 信息科学版, 1984, 9(2): 29-41.

点击查看大图

计量

文章访问数: 826
HTML全文浏览量: 57
PDF下载量: 630
被引次数: 0

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

¹西南交通大学土木工程学院测量工程系,成都市二环路北一段111号610031;²昆明冶金高等专科学校测绘学院,昆明市学府路388号,650033;²昆明理工大学国土资源工程学院,昆明市文昌路68号650093;⁴昆明理工大学教育技术与网络中心,昆明市文昌路68号650093

基金项目: 云南省应用基础研究面上资助项目(2009CD102)

作者简介:
马娟,博士生,讲师,主要从事三维GIS理论及应用研究。

收稿日期: 2011-01-25
刊出日期: 2011-03-05

中图分类号: P208

关键词:

离散数据 /

k近邻 /

空间微分块 /

动态球

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