CAJ | 학술논문

kD 树是近邻搜索中应用最广泛的算法之一，针对其性能随着空间维度的增加而迅速降低的问题，提出一种可应用到高维空间的kD树搜索算法——okD树。在该okD树的创建过程中，左右子结点之间保留重叠区域，重叠区域不参与后续的划分而是直接传递到子结点；在搜索过程中，对于存在重叠区域的子结点不进行回溯，以提高 okD树的搜索效率，不进行回溯的子结点中包含的重叠区域扩大了搜索范围，从而提高了搜索精度。实验结果表明 okD树算法的性能优于当前主流的近似kD树算法。
kD 수시근린수색중응용최엄범적산법지일，침대기성능수착공간유도적증가이신속강저적문제，제출일충가응용도고유공간적kD수수색산법——okD수。재해okD수적창건과정중，좌우자결점지간보류중첩구역，중첩구역불삼여후속적화분이시직접전체도자결점；재수색과정중，대우존재중첩구역적자결점불진행회소，이제고 okD수적수색효솔，불진행회소적자결점중포함적중첩구역확대료수색범위，종이제고료수색정도。실험결과표명 okD수산법적성능우우당전주류적근사kD수산법。
ThekD tree is one of the most popular algorithms for searching the nearest neighbor, but its per-formance degrades quickly in high dimensional space. An overlapkD(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 con-sequently improve the search accuracy. Experimental results show that the okD tree achieves a higher per-formance than other approximatekD tree algorithms.