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

J4 ›› 2011, Vol. 33 ›› Issue (8): 167-172.

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

赵清华，陈荦，景宁

(国防科学技术大学电子科学与工程学院，湖南长沙 410073)

收稿日期:2009-09-07 修回日期:2009-12-15 出版日期:2011-08-25 发布日期:2011-08-25
作者简介:赵清华(1984),男,湖南长沙人，硕士生，研究方向为空间信息服务。陈荦(1973),男，湖南长沙人，副教授，研究方向为地理信息系统和分布式数据库。景宁(1963),男，湖南长沙人，博士，教授，研究方向为地理信息系统和空间数据库技术。
基金资助:
国家自然科学基金资助项目（40601080）；国家863计划资助项目（2008A12AA211，2007AA12Z208）

Distributed Spatial Join Query Based on Kd-Tree Recursive Partitioning

ZHAO QingHua，CHEN Luo，JING Ning

(School of Electronics Science and Engineering,
National University of Defense Technology,Changsha 410073,China)

Received:2009-09-07 Revised:2009-12-15 Online:2011-08-25 Published:2011-08-25

摘要/Abstract

摘要：

随着空间信息应用需求的不断增长，分布式空间查询处理已经成为空间数据库领域一个重要的研究问题，其中应用最广也是最复杂的一类查询是分布式空间连接查询，分布式空间连接操作的计算代价与传输代价都非常高。目前处理该问题的策略大都要求空间数据集上存在索引并且对数据分布敏感，然而在某些情况下，这个前提并不存在。面对这个问题，本文提出一种基于Kd树递归区域划分的分布式空间连接策略，该策略以最小化网络数据传输代价为目标，基于任务分治的思想对连接区域进行递归划分。实验表明，该策略在不同数据分布情况下均优于传统查询策略，能有效地减小网络传输代价，表现出较好的性能。

关键词: 空间连接查询, Kd树, 分布式

Abstract:

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.

Key words: saptial join query;kdtree;distribute

赵清华，陈荦，景宁. 基于Kd树递归区域划分的分布式空间连接查询[J]. J4, 2011, 33(8): 167-172.

ZHAO QingHua，CHEN Luo，JING Ning. Distributed Spatial Join Query Based on Kd-Tree Recursive Partitioning[J]. J4, 2011, 33(8): 167-172.

[1]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(06): 959-967.
[2]	黄泽彪, 董德尊, 齐星云. Gloo+：利用在网计算技术加速分布式深度学习训练[J]. 计算机工程与科学, 2024, 46(01): 28-36.
[3]	周小华, 王学志, 周园春, 孟珍, . 面向大区域碳卫星数据的分布式Kriging插值算法优化[J]. 计算机工程与科学, 2023, 45(11): 1911-1921.
[4]	姚袭欣, 章博, 陈香兰, 乔磊, 李曦. 一种基于Event-B语言的时间触发系统建模方法[J]. 计算机工程与科学, 2023, 45(04): 613-621.
[5]	白耀文, 杜亚江, 李宗刚, . 基于多步长的多机器人分布式巡逻算法研究[J]. 计算机工程与科学, 2023, 45(02): 313-320.
[6]	王笑雨, 董德尊. 一种面向分布式深度学习的轻量级聚合通信库[J]. 计算机工程与科学, 2022, 44(07): 1191-1198.
[7]	沈佳杰, 卢修文, 向望, 赵泽宇, 王新, . 分布式存储系统读写一致性算法性能优化研究综述[J]. 计算机工程与科学, 2022, 44(04): 571-583.
[8]	周静, 关玉蓉. 基于SDN的DWSN技术分析及性能优化研究[J]. 计算机工程与科学, 2021, 43(08): 1413-1421.
[9]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[10]	季航旭, 姜苏, 赵宇海, 吴刚, 王国仁. 分布式环境中的多作业执行调度策略与优化[J]. 计算机工程与科学, 2021, 43(06): 951-961.
[11]	朱良杰, 沈佳杰, 周扬帆, 王新, . 云际存储系统性能优化研究现状与展望[J]. 计算机工程与科学, 2021, 43(05): 761-772.
[12]	魏嘉, 张兴军, 纪泽宇, 李靖波, 岳莹莹. 天河三号原型机分布式并行深度神经网络性能评测及调优[J]. 计算机工程与科学, 2021, 43(05): 782-791.
[13]	曾杰, 贲可荣, 张献, 徐永士. 融合文本分布式表示的重复缺陷报告检测[J]. 计算机工程与科学, 2021, 43(04): 670-680.
[14]	张立志, 冉浙江, 赖志权, 刘锋. 分布式深度学习通信架构的性能分析[J]. 计算机工程与科学, 2021, 43(03): 416-425.
[15]	牛淑芬, 王金风, 王伯彬, 陈敬民, 杜小妮. 区块链上支持多关键字检索的可搜索加密方案[J]. 计算机工程与科学, 2020, 42(11): 2005-2012.