Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations
Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations
复制标题
DOI：
--
复制
发表时间：
1997-08
期刊：
影响因子：
--
通讯作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
中科院分区：
文献类型：
--
作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
基于r树的空间连接非常有用，因为它具有优越的性能和r树的广泛实现。提出了一种新的r树连接方法，称为BFRJ（宽度优先r树连接）。BFRJ以宽度优先的顺序同步遍历两个r树，同时每次处理一级连接计算。在每一层，BFRJ创建一个中间连接索引，并部署全局优化策略（排序、内存管理、缓冲区管理），以改进下一层的连接计算。我们还对所提出的优化进行了实验评估，并对BFRJ和最先进方法之间的性能进行了比较。我们的实验结果表明，经过全局优化的BFRJ可以显著优于竞争对手（高达50%）。这项工作得到了密歇根大学ITS研究中心卓越基金（DTFH61-93-X0001i ' -Sub）的部分支持，该基金由美国交通部和密歇根州交通部赞助。这项研究是作者在密歇根大学期间进行的。允许免费复制本材料的所有部分，前提是这些副本不是为了直接的商业利益而制作或分发的，必须有VLDB版权声明、出版物标题和出版日期，并注明复制是由超大型数据库基金会许可的。以其他方式复制或重新发布，需要支付费用和/或捐赠基金的特别许可。第23届世界开发银行会议记录，希腊雅典，1997年
R-tree based spatial join is useful because of both its superior performance and the wide spread implementation of R-trees. We present a new R-tree join method called BFRJ (Breadth-First R-tree Join). BFRJ synchronously traverses both R-trees in breadthfirst order while processing join computation one level at a time. At each level, BFRJ creates an intermediate join index and deploys global optimization strategies (ordering, memory management, buffer management) to improve the join computation at the next level. We also present an experimental evaluation of the proposed optimizations as well as a performance comparison between BFRJ and the state-of-the-art approach. Our experimental results indicate that BFRJ with global optimizations can outperform the competitor by a significant margin (up to 50%). This work was supportedin part by the University of Michigan ITS Research Center of Excellence grant (DTFH61-93-X0001i’-Sub) sponsored by the U.S. Dept. of Transportation and by the Michigan Dept. of Transportation. This work was performed while the authors were at the University of Michigan. Permission to copy without fee all OT part of this material is granted provided that the copies are not made OT distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, OT to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 23rd VLDB Conference Athens, Greece, 1997