广东工业大学学报 ›› 2014, Vol. 31 ›› Issue (3): 119-123.doi: 10.3969/j.issn.1007-7162.2014.03.021
陈晓康,刘竹松
Chen Xiao-kang,Liu Zhu-song
摘要: k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率.但是,传统的Kd-Tree构建有两个缺点:使用测试数据点进行k近邻查询每次都需要回溯到根节点,影响了查询的效率;Kd-Tree使用split域对空间进行层次划分,空间划分为立方体(二维数据表现为矩形),多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间,这样会影响查询的效率.针对这两个缺点,本文提出了相应的改进算法——RB算法.实验结果证明,该算法比传统的KD算法拥有更高的查询效率.本文的主要贡献有两点:(1)构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作.(2)改进传统的Kd-Tree索引构建方法,提出新的改进算法RB算法,提高KNN算法查询的效率.
No related articles found! |
|