多路空间连接优化算法研究  

Research of Optimization Algorithm for Multi-way Spatial Join

作　　者：汪璟玢[1] 彭志星[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108

出　　处：《小型微型计算机系统》2013年第11期2431-2436,共6页Journal of Chinese Computer Systems

基　　金：空间数据挖掘与信息共享教育部重点实验室开放研究基金项目(201006)资助;福建省自然科学基金项目(2012J01168)资助

摘　　要：在深入分析各种空间连接算法特点的基础上,提出一种可以有效提高多路空间连接效率的优化方法.该方法一方面针对空间数据的聚类特性,提出了获得更加紧凑的R树索引结构的算法;另一方面考虑连接顺序对多路空间连接算法性能的影响,提出基于R树连接的多路空间限制策略和多路平面扫描技术,从而优化数据集参与连接的顺序选择,并在此基础上给出优化的多路连接算法.通过实验验证,本文的优化方法能够有效的提高多路空间连接查询效率,尤其是在耗时较大的链图查询上.The paper puts forward a kind of optimization method which can effectively improve the efficiency of multi-way spatial join query, based on in-depth analysis of various spatial join algorithm characteristics. On the one hand, in view of the clustering feature of the spatial data, the paper proposes a new method of constructing R-tree with more compact structure; on the other hand, in the process of multi-way spatial join, the join order selection has large impacts on the performance of join, so we put forward restriction of the search space and plane sweep in multi-way spatial joins based on R-trees to optimize the join order selection, and then, we present the optimization algorithm for multi-way spatial joins. The experimental results show that, this optimization method can effectively im-prove the efficiency of spatial join query, especially on chain diagram query which is time-consuming.

关 键 词：空间连接查询 空间索引 R-树 空间数据 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]