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

Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query

作　　者：李松[1] 李林 王淼[1,3] 崔环宇[1] 张丽平[1] 

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

出　　处：《计算机应用》2015年第1期115-120,共6页journal of Computer Applications

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

摘　　要：空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形（MBR）、梯形和圆的新的索引结构（RTC树）。为了有效处理复杂空间数据对象的最近邻（NN）关系查询问题,提出了基于RTC树的最近邻查询（NNRTC）算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算。针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询（BNNRTC）算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断。为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询（SCNNCRTC）算法。实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率。The spatial index structure and the query technology plays an important role in the spatial database. According to the disadvantages in the approximation and organization of the complex spatial objects of the existing methods, a new index structure based on Minimum Bounding Rectangle（ MBR）, trapezoid and circle（ RTC（ Rectangle Trapezoid Circle） tree） was proposed. To deal with the Nearest Neighbor（ NN） query of the complex spatial data objects effectively, the NN query based on RTC（ NNRTC） algorithm was given. The NNRTC algorithm could reduce the nodes traversal and the distance calculation by using the pruning rules. According to the influence of the barriers on the spatial data set, the barrier-NN query based on RTC tree（ BNNRTC） algorithm was proposed. The BNNRTC algorithm first queried in an idea space and then judged the query result. To deal with the dynamic simple continuous NN chain query, the Simple Continues NN chain query based on RTC tree（ SCNNCRTC） algorithm was given. The experimental results show that the proposed methods can improve the efficiency of 60%- 80% in dealing with large complex spatial object data set with respect to the query method based on R tree.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]