一种优化的空间连接算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (12): 117-121.

• 数据库、信号与信息处理 • 上一篇下一篇

一种优化的空间连接算法

邹永贵，徐海波，梁新发，杨富平

重庆邮电大学中韩合作GIS研究所，重庆 400065

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-04-21 发布日期:2011-04-21

Optimal spatial join algorithm

ZOU Yonggui，XU Haibo，LIANG Xinfa，YANG Fuping

Sino-Korea Chongqing GIS Research Center，Chongqing University of Posts and Telecommunications，Chongqing 400065，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-21 Published:2011-04-21

摘要/Abstract

摘要： 空间数据库中空间连接操作是最重要、最耗时的操作之一，基于BFRJ算法研究了一种对中间连接索引优化排序的空间连接算法OBFRJ，该算法使用广度优先顺序对两棵R树进行同步遍历，对生成的中间连接索引采用了一种空间填充曲线进行排序，使得在下一层的连接时出现页错误的次数减少。实验结果表明，该算法在磁盘访问次数以及CPU代价上都要小于DFRJ和BFRJ算法。

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

Abstract: 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.

Key words: spatial database, spatial join, R-tree, space-filling curve, plane sweeping

邹永贵，徐海波，梁新发，杨富平. 一种优化的空间连接算法[J]. 计算机工程与应用, 2011, 47(12): 117-121.

ZOU Yonggui，XU Haibo，LIANG Xinfa，YANG Fuping. Optimal spatial join algorithm[J]. Computer Engineering and Applications, 2011, 47(12): 117-121.

[1]	马菁1，2，李力3. RDD上扩展索引层优化的分布式K-means算法[J]. 计算机工程与应用, 2019, 55(1): 161-167.
[2]	杨泽雪. 空间数据库中的一种混合索引结构的研究[J]. 计算机工程与应用, 2017, 53(20): 20-23.
[3]	周屹1，杨泽雪1，2. 空间数据库中的线段k近邻查询研究[J]. 计算机工程与应用, 2015, 51(18): 131-134.
[4]	张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
[5]	徐红波1，2，姚念民2，韩启龙2，潘海为2. 支持线段查询索引结构CB树[J]. 计算机工程与应用, 2015, 51(11): 114-118.
[6]	汪璟玢. 一种结合空间聚类算法的R树优化算法[J]. 计算机工程与应用, 2014, 50(5): 112-115.
[7]	肖邱勇，李光强. 空间数据库性能对比实验分析[J]. 计算机工程与应用, 2014, 50(21): 139-142.
[8]	刘维群，李元臣. 基于局部信息的时延和时延差约束的组播路由[J]. 计算机工程与应用, 2012, 48(34): 76-80.
[9]	林键，刘仁义，刘南，张丰. 基于查询优化器的分布式空间查询优化方法[J]. 计算机工程与应用, 2012, 48(22): 161-165.
[10]	张丽平，李松，郝忠孝. 球面上的最近邻查询方法研究[J]. 计算机工程与应用, 2011, 47(5): 126-129.
[11]	杨泽雪1，3，郝忠孝1，2. 空间数据库中的障碍反向最近邻查询[J]. 计算机工程与应用, 2011, 47(34): 130-133.
[12]	李进，余建桥. 空间对象的反最近邻查询处理技术研究[J]. 计算机工程与应用, 2011, 47(33): 146-148.
[13]	徐红波1，韩启龙2，潘海为2. 空间数据库最优位置查询算法研究[J]. 计算机工程与应用, 2011, 47(18): 19-21.
[14]	冯春生. 2维空间填充曲线的块矩阵迭代法[J]. 计算机工程与应用, 2011, 47(12): 36-38.
[15]	文元桥¹，周春辉². 基于ArcSDE的空间拓扑关系连接方法研究[J]. 计算机工程与应用, 2010, 46(5): 117-119.

一种优化的空间连接算法

Optimal spatial join algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics