基于Kd树递归区域划分的分布式空间连接查询  

Distributed Spatial Join Query Based on Kd-Tree Recursive Partitioning

作　　者：赵清华[1] 陈荦[1] 景宁[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,湖南长沙410073

出　　处：《计算机工程与科学》2011年第8期167-172,共6页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(40601080);国家863计划资助项目(2008A12AA211;2007AA12Z208)

摘　　要：随着空间信息应用需求的不断增长,分布式空间查询处理已经成为空间数据库领域一个重要的研究问题,其中应用最广也是最复杂的一类查询是分布式空间连接查询,分布式空间连接操作的计算代价与传输代价都非常高。目前处理该问题的策略大都要求空间数据集上存在索引并且对数据分布敏感,然而在某些情况下,这个前提并不存在。面对这个问题,本文提出一种基于Kd树递归区域划分的分布式空间连接策略,该策略以最小化网络数据传输代价为目标,基于任务分治的思想对连接区域进行递归划分。实验表明,该策略在不同数据分布情况下均优于传统查询策略,能有效地减小网络传输代价,表现出较好的性能。With the growth of the application of spatial information,distributed spatial query has become an important question of the spatial database research field,of which the most widely used and most complex is the distributed spatial join queries,and the computational cost and transport cost are very high.The common methods to dissolve this question requires a spatial index on the data sets and sensitivity to distributed data,which is not satisfied in most cases.Considering this issue,the paper proposes a distributed spatial join strategy based on the Kd-tree Recursive Partitioning Join,which is aimed at minimizing the cost of network data transmission,and recursively divides the adjacent regions based on task partitioning.The experiments demonstrate that this strategy is better than the traditional ones in different data distribution cases,which is effective in reducing network transmission costs and presents better performance.

关 键 词：空间连接查询 KD树 分布式 

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