基于重叠区域的高性能近似kD树算法  

A High Performance Approximate k D Tree with Overlap

作　　者：郑明玲[1] 许柯[2] 刘衡竹[1] 魏登萍[1] 李宝峰[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073 [2]湖南警察学院信息技术系,长沙410077

出　　处：《计算机辅助设计与图形学学报》2015年第6期1053-1059,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61202118);国家"八六三"高技术研究发展计划(2012AA01A301)

摘　　要：kD树是近邻搜索中应用最广泛的算法之一,针对其性能随着空间维度的增加而迅速降低的问题,提出一种可应用到高维空间的kD树搜索算法——okD树.在该okD树的创建过程中,左右子结点之间保留重叠区域,重叠区域不参与后续的划分而是直接传递到子结点;在搜索过程中,对于存在重叠区域的子结点不进行回溯,以提高okD树的搜索效率,不进行回溯的子结点中包含的重叠区域扩大了搜索范围,从而提高了搜索精度.实验结果表明okD树算法的性能优于当前主流的近似kD树算法.The kD tree is one of the most popular algorithms for searching the nearest neighbor, but its performance degrades quickly in high dimensional space. An overlap kD（okD） tree is proposed to address this problem, which can be used in high dimensional space. In the process of constructing the okD tree, overlaps are allowed between two child nodes, and these overlaps are not split and directly passed to the successors in the following partition procedure. In the process of traversing the okD tree, the nodes with overlap are not backtracked to improve the efficiency, and the overlaps in these nodes enlarge the search scale, which consequently improve the search accuracy. Experimental results show that the okD tree achieves a higher performance than other approximate kD tree algorithms.

关 键 词：KD树 重叠区域 搜索精度 搜索效率 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]