摘要
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.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2015年第6期1053-1059,共7页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金(61202118)
国家"八六三"高技术研究发展计划(2012AA01A301)
