基于改进Kd-Tree构建算法的k近邻查询

• 作者: 刘竹松 陈晓康
• 来源期刊: 广东工业大学学报
• 学科: 工学
• 关键词: k近邻查询 Kd树 空间数据 多边形空间 层次划分
• 年，卷（期）: 2014,（3）
• 页码范围: 119-123
• 页数: 5页
• 分类号: TP311
• 字数: 3033字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-7162.2014.03.021

摘要

k近邻查询算法是查询大规模空间数据的常用算法之一，使用Kd-Tree先构建大规模空间数据的索引，然后对搜索空间进行层次划分，再进行k近邻查询，能保证搜索的效率。但是，传统的Kd-Tree构建有两个缺点：使用测试数据点进行k近邻查询每次都需要回溯到根节点，影响了查询的效率；Kd-Tree使用split域对空间进行层次划分，空间划分为立方体（二维数据表现为矩形），多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间，这样会影响查询的效率。针对这两个缺点，本文提出了相应的改进算法---RB算法。实验结果证明，该算法比传统的KD算法拥有更高的查询效率。本文的主要贡献有两点：（1）构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作。（2）改进传统的Kd-Tree索引构建方法，提出新的改进算法RB算法，提高KNN算法查询的效率。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘竹松	广东工业大学计算机学院	43	252	9.0	14.0
2	陈晓康	广东工业大学计算机学院	1	16	1.0	1.0