并行环境下基于图着色理论的空间数据部署

吉林大学学报(理学版)

并行环境下基于图着色理论的空间数据部署

殷君茹¹, 唐小明¹, 李惺颖², 卜祥亮³

1. 中国林业科学研究院资源信息研究所, 北京100091; 2. 广西林业勘测设计院 3S技术研究与开发中心, 南宁 530011; 3. 北京林业大学水土保持学院, 北京 100083

收稿日期:2014-10-28 出版日期:2015-05-26 发布日期:2015-05-21
通讯作者: 唐小明 E-mail:tangxm@caf.ac.cn

Graph Coloring Based Spatial Data Placement towards Parallel Computing System

YIN Junru^1, TANG Xiaoming^1, LI Xingying^2, BU Xiangliang^3

1. Research Institute of Resource Information Techniques, Chinese Academy of Forestry, Beijing 100091, China;2. RS, GIS, GPS Technology Research & Development Center, Guangxi Forest Inventory & Planning Institute, Nanning 530011, China; 3. College of Soil and Water Conservation, Beijing Forestry University, Beijing 100083, China

Received:2014-10-28 Online:2015-05-26 Published:2015-05-21
Contact: TANG Xiaoming E-mail:tangxm@caf.ac.cn

摘要/Abstract

摘要：

在面向计算部署到数据节点端执行的分布式并行环境下, 提出一种基于图着色理论的适用于矢量空间数据的部署方法, 将空间数据粒度的部署问题转化为图顶点着色的过程, 提高了任意空间区域的信息查询效率. 给出基于图着色理论的数据部署方法, 并通过节点的任务量进一步改进算法, 使得该算法可实现海量空间数据粒度的离散化部署, 提高了空间数据检索和查询的并行化程度, 充分利用了并行计算资源.

关键词: 空间数据部署, 数据粒度, 并行环境, 图着色理论, 负载均衡

Abstract:

An algorithm suitable for spatial vector data placement based on graph coloring theory was presented in the parallel system of computing distributed to data nodes. The deployment problem was transferred into graph vertex coloring problem, and the information query efficiency of any spatial area was thus improved. Moreover, the algorithm based on graph vertex coloring problem was proposed and improved by the task of nodes. This algorithm can achieve discrete deployment of massive spatial data granularity and storage load balance of the nodes, improve the degree of parallelism spatial data retrieval and query, and make full use of parallel computing resources.

Key words: spatial data placement, data granularity, parallel computing system, graph coloring theory, load balancing

中图分类号:

TP391

殷君茹, 唐小明, 李惺颖, 卜祥亮. 并行环境下基于图着色理论的空间数据部署[J]. 吉林大学学报(理学版), 2015, 53(03): 525-530.

YIN Junru, TANG Xiaoming, LI Xingying, BU Xiangliang. Graph Coloring Based Spatial Data Placement towards Parallel Computing System[J]. Journal of Jilin University Science Edition, 2015, 53(03): 525-530.

[1]	王出航, 王雪, 胡黄水, 赵宏伟, 韩由佳. 基于改进GA和信任感知的无线传感器网络安全分簇路由协议[J]. 吉林大学学报(理学版), 2021, 59(5): 1237-1244.
[2]	吴佳楠, 吴剑, 邸焕双, 王玉英, 李念峰. 基于逻辑分区的仿箱鲀鱼群负载均衡分簇控制算法[J]. 吉林大学学报(理学版), 2020, 58(6): 1407-1414.
[3]	管乃彦, 郭娟利. 异构环境下高速互联网络覆盖优化控制算法[J]. 吉林大学学报(理学版), 2020, 58(2): 343-348.
[4]	袁赫潞, 温长吉, 吴建双, 朱允刚, 于合龙. 基于遗传珊瑚礁优化算法的负载均衡问题[J]. 吉林大学学报(理学版), 2019, 57(06): 1465-1471.
[5]	王出航, 沈玮娜, 胡黄水. 基于分布式模糊控制器的无线传感器网络容错非均匀分簇算法[J]. 吉林大学学报(理学版), 2018, 56(3): 631-638.
[6]	姜彬彬, 于寒. 综合负载均衡与能量消耗的无线传感器网络分簇算法[J]. 吉林大学学报(理学版), 2017, 55(06): 1552-1556.
[7]	任长安, 赵巾帼, 罗庆云. 云计算资源优化问题求解的萤火虫算法[J]. 吉林大学学报(理学版), 2017, 55(05): 1234-1238.
[8]	宋俊辉, 冯岩. 负载均衡的分布式系统任务调度优化算法[J]. 吉林大学学报(理学版), 2017, 55(02): 383-387.
[9]	匡珍春, 谢仕义. 基于猫群优化算法的云计算虚拟机资源负载均衡调度[J]. 吉林大学学报(理学版), 2016, 54(05): 1117-1122.
[10]	李晟彬, 唐小明, 李志清, 殷君茹, 李惺颖. 基于并行计算的多副本空间数据离散布局策略[J]. 吉林大学学报(理学版), 2016, 54(03): 524-528.
[11]	殷君茹, 侯瑞霞, 唐小明, 罗鹏. 基于瓦片金字塔模型的海量空间数据快速分发方法[J]. 吉林大学学报(理学版), 2015, 53(06): 1269-1274.
[12]	张腊, 刘淑芬, 韩璐. 基于负载均衡的任务调度算法[J]. 吉林大学学报(理学版), 2014, 52(04): 769-772.