RTC树的构建与不确定近邻关系查询方法

来源：计算机应用杂志2015年第1期北京时间：

作者：李松, 李林, 王淼, 崔环宇, 张丽平

单位：1. 哈尔滨理工大学 计算机科学与技术学院, 哈尔滨150080;2. 诺基亚通信系统技术有限公司 TDLTE测试部, 杭州310000;3. 河南工程学院 计算机科学与工程系, 郑州451191

摘要：空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.

关键词：空间数据库,R树,RTC树,最近邻,单纯型连续近邻链

基金资助：黑龙江省教育厅科学技术研究项目(12541128).