云环境下顾及空间子域分布特征的空间大数据并行计算方法研究

摘要

空天地立体观测与移动互联网技术的蓬勃发展带来爆炸式增长的空间大数据，迫使空间分析计算模式从集中式处理、单人机交互向高扩展性、高效性、数据多源性方向转变。利用云计算资源实现空间大数据并行化处理是完成这一模式转变的重要途径。云环境下的并行计算范式本质上是一种单指令多数据流并行，该范式要求将数据集划分成独立的无共享的部分并行处理。然而，空间数据具有组织异构、分布不均衡、实体关联性强等特点，这导致空间数据无法直接分割以适应云环境下的并行计算范式，传统的并行空间计算方法大多面向特定的应用场景，缺乏对空间实体关联关系及分布特征的考虑，未能形成包括空间大数据组织存储、划分计算、效率优化等在内的并行计算方法体系。
　　针对以上问题，本文开展了顾及空间子域分布特征的空间大数据并行计算方法体系研究，提出了不同空间子域分布特征的空间操作数据划分策略与并行化方法，以实际空间计算场景为例，采用真实的空间大数据集对本文提出的方法进行了正确性与高效性验证，为云环境下亿级空间大数据计算提供了方法支撑与案例借鉴。本文的研究内容概括如下:
　　(1)遵循云环境下并行计算范式要求，设计了空间数据云存储组织与并行空间计算统一流程表达方法，研究了面向数据划分的空操作分类及其空间子域分布特征，提出了空间子域的任务计算量评估方法，形成完整的并行空间计算方法体系。
　　(2)在上述基础上，针对本地空间操作的特性，设计了基于默认子域和基于格网子域的两种通用本地空间操作数据划分方法，基于这两种方法实现了空间频率图和多级金字塔矢量图的并行绘制，以十亿级全球兴趣点与百万级矢量多边形为测试数据对比验证了方法的适用性与高效性。
　　(3)提出了邻域空间操作的三种规则空间子域分布形态:范围分布的规则空间子域、范围时空分布的规则空间子域、异构数据叠加误差导致的规则空间子域，对上述三种子域分布特性的空间操作分别设计了并行化方法，分别以空间距离连接、时空热点分析、大规模三维地表表面积计算为案例验证了方法的适用性与高效性。
　　(4)针对空间子域不规则分布的邻域空间操作的特点，以K邻近连接为例，提出了基于格网均匀扩张的不规则空间子域范围确定方法和基于Voronoi的不规则空间子域范围确定方法，在此基础上实现了K邻近连接的并行化算法，通过性能实验对比了两种方法的适用性与高效性。

目录

声明

致谢

摘要

图索引

表索引

符号表

1 绪论

1．1 研究背景与意义

1．1．1 空间大数据的来源

1．1．2 空间大数据并行计算的必要性

1．1．3 空间大数据并行计算的关键挑战

1．1．4 研究意义

1．2 相关工作与研究现状

1．2．1 云计算在“大数据”中的应用

1．2．2 空间数据分析及其应用

1．2．3 空间大数据并行计算的技术主线

1．2．4 空间大数据并行计算方法综合评述

1．3 研究内容与章节安排

1．3．1 研究内容

1．3．2 章节安排

2 顾及空间子域分布特征的空间大数据并行计算方法体系

2．1 云环境下的并行计算范式

2．1．1 无约束并行与子作业依赖关系

2．1．2 MapReduee并行计算模型

2．1．3 弹性分布式数据集计算模型

2．2 面向并行计算的异构空间数据云存储组织方法

2．2．1 空间数据表示模型

2．2．2 基于key-value的空间数据云存储组织方法

2．3 基于操作解构的并行空间计算流程表达

2．3．1 空间子域划分

2．3．2 任务分发

2．3．3 子任务执行

2．3．4 结果合并

2．4 面向解构的空间操作分类及其空间子域分布特征

2．4．1 本地空间操作及其空间子域分布特征

2．4．2 规则邻域空间操作及其空间子域分布特征

2．4．3 不规则邻域空间操作及其空间子域分布特征

2．5 空间子域的任务计算量评估

2．5．1 多维度空间子域任务计算量表示

2．5．2 空间子域计算代价评估

2．6 本章小结

3 本地空间操作的数据划分与并行化方法

3．2 基于格网子域的本地空间操作数据划分-GSBD

3．3 基于DSBD与GSBD的空间频率图并行绘制

3．3．1 数据划分

3．3．2 子任务执行

3．3．3 图像绘制

3．3．4 结果合并

3．4 基于GSBD的金字塔矢量图并行绘制算法

3．4．1 金字塔矢量图

3．4．2 金字塔矢量图并行绘制算法实现

3．5 实验与分析

3．5．1 实验环境

3．5．2 DSBD与GSBD的性能分解对比

3．5．3 金字塔矢量图计算性能分析

3．6 本章小结

4 空间子域规则分布的邻域空间操作数据划分与并行化方法

4．1 面向空间范围连接的规则邻域空间操作并行化方法-RDJOD

4．1．1 空间范围连接定义

4．1．2 空间实体邻域范围确定

4．1．3 基于格网子域的空间数据划分

4．1．4 RDDs模型上εRDJ并行化实现

4．2 面向时空立方体的规则邻域空间操作并行化方法-SCOD

4．2．1 时空立方体构建

4．2．2 时空立方体邻域范围确定

4．2．3 时空立方体子域划分

4．3 基于SCOD的大规模时空热点分析并行计算

4．3．1 时空热点

4．3．2 总体执行流程

4．3．3 热度值计算

4．3．4 多视角出租车轨迹热点识别

4．4 面向异构数据叠加计算的空间子域划分与并行化-SDHDOC

4．4．1 异构数据并行叠加计算的总体执行流程

4．4．2 空间子域划分

4．4．3 基于空间子域缓存的异构数据叠加

4．5 基于SDHDOC的大规模地表表面积统计并行化算法

4．5．1 地表覆盖表面积计算实现原理

4．5．2 基于SDHDOC的地表表面积并行计算

4．6 实验与分析

4．6．1 SCOD计算实验与分析

4．6．2 基于SDHDOC的大规模地表表面积统计实验与分析

4．7 本章小结

5 空间子域不规则分布的邻域空间操作数据划分与并行化方法

5．1．1 基本概念

5．1．2 不规则空间子域范围确定

5．2 基于UGE的KNNJ并行化实现

5．3 基于Voronoi的不规则空间子域范围确定方法-Voronoi

5．3．1 Voronoi的几何特性

5．3．2 控制点选取策略

5．3．3 不规则空间子域范围确定

5．4 Voronoi KNNJ并行化实现

5．5 实验与分析

5．5．1 控制点选取

5．5．2 K值对计算性能的影响

5．5．3 Voronoi-KNNJ与UGE-KNNJ计算性能对比

5．6 本章小结

6 结论与展望

6．1 内容总结

6．2 研究特色

6．3 工作展望

参考文献

作者简历