一种基于广度优先策略的R树连接算法

R-tree spatial join algorithm based on the breath-first paradigm

研究了一种基于广度优先搜索的层内分组扫描策略的R树空间连接新算法.BFGS采用广度优先的顺序对两棵R树进行同步遍历,在处理每层的中间连接索引时采取了比逐个节点连接更好的层内优化策略,使得所生成的中间连接索引自动被排序,从而减少了对其的处理时间.实验结果表明,无论是I/O时间还是CPU时间,BFGS都胜过RJ和BFRJ算法,比RJ算法的速度快了15 .5 %～33.1% ,证明BFGS是一种高效的R树空间连接算法.

R-tree spatial join algorithm BFGS (Breadth-First Group-based Sweeping) was introduced based on the breath-first group-based plane sweeping paradigm. The BFGS algorithm scans the two R-trees involved in spatial join with breadth-first order. While the intermediate join index (IJI) was processed, the group-based plane sweeping paradigm which was better than the traditional node-by-node join strategy was used in BFGS algorithm. The IJI was automatically arranged and required less processing time. Compared with the RJ and BFRJ algorithms, the BFGS algorithm uses less I/O time and CPU time. The BFGS algorithm, which is 15.5?%～33.1?% faster than the RJ algorithm, was proved to be an efficient R-tree spatial join algorithm.