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

• 作者: 刘衡竹 李宝峰 许柯 郑明玲 魏登萍
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: kD树 重叠区域 搜索精度 搜索效率
• 年，卷（期）: 2015,（6）
• 所属期刊栏目: 图像与视觉
• 页码范围: 1053-1059
• 页数: 7页
• 分类号: TP391
• 字数: 5145字
• 语种: 中文

摘要

kD 树是近邻搜索中应用最广泛的算法之一，针对其性能随着空间维度的增加而迅速降低的问题，提出一种可应用到高维空间的kD树搜索算法——okD树。在该okD树的创建过程中，左右子结点之间保留重叠区域，重叠区域不参与后续的划分而是直接传递到子结点；在搜索过程中，对于存在重叠区域的子结点不进行回溯，以提高 okD树的搜索效率，不进行回溯的子结点中包含的重叠区域扩大了搜索范围，从而提高了搜索精度。实验结果表明 okD树算法的性能优于当前主流的近似kD树算法。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘衡竹	国防科技大学计算机学院	19	193	9.0	13.0
2	郑明玲	国防科技大学计算机学院	4	58	3.0	4.0
3	魏登萍	国防科技大学计算机学院	8	53	4.0	7.0
4	许柯	湖南警察学院信息技术系	5	22	3.0	4.0
5	李宝峰	国防科技大学计算机学院	3	14	2.0	3.0