一种优化的空间连接算法  

Optimal spatial join algorithm

作　　者：邹永贵[1] 徐海波[1] 梁新发[1] 杨富平[1] 

机构地区：[1]重庆邮电大学中韩合作GIS研究所,重庆400065

出　　处：《计算机工程与应用》2011年第12期117-121,共5页Computer Engineering and Applications

基　　金：国家自然科学基金项目No.40801214~~

摘　　要：空间数据库中空间连接操作是最重要、最耗时的操作之一,基于BFRJ算法研究了一种对中间连接索引优化排序的空间连接算法OBFRJ,该算法使用广度优先顺序对两棵R树进行同步遍历,对生成的中间连接索引采用了一种空间填充曲线进行排序,使得在下一层的连接时出现页错误的次数减少。实验结果表明,该算法在磁盘访问次数以及CPU代价上都要小于DFRJ和BFRJ算法。Spatial. join is one of the most important and time-consuming operations.A new R-tree spatial join algorithm based on Breadth-First R-tree Join（BFRJ）,named OBFRJ, is proposed.The OBFRJ algorithm scans the two R-tree involved in spatial join in breadth-first order.While the intermediate join index is being processed,the OBFRJ adopts a space filling curve to order it,hence reducing the chance of page faults during the join operation of the next layer.Compared with the DFRJ and BFRJ algorithms,this method reduces the frequency of disk access and the overhead of CPU.

关 键 词：空间数据库 空间连接 R树 空间填充曲线 平面扫描 

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