第1章 绪论 1
1.1 时空数据模型 1
1.1.1 时空数据模型的研究意义 1
1.1.2 时空数据模型的研究现状 3
1.1.3 已有时空数据模型的分类 3
1.1.4 已有时空数据模型的局限性 5
1.2 时态GIS与并行GIS 6
1.2.1 时态GIS 6
1.2.2 并行GIS 6
1.2.3 时态GIS与并行GIS需要集成 7
1.3 数字城市 7
1.3.1 数字城市的研究意义 7
1.3.2 数字城市的研究现状 8
1.3.3 数字城市的已有技术 10
1.3.4 现有数字城市需要并行 11
1.4 并行计算 12
1.4.1 并行数据挖掘 12
1.4.2 并行交通仿真 13
1.4.3 并行视频压缩 13
1.4.4 已有并行研究在时空中不足 14
1.5 本书的内容 14
1.6 本书的组织 15
第2章 并行时空模型的理论基础 16
2.1 时空模型 16
2.1.1 时空立方体模型 16
2.1.2 序列快照模型 17
2.1.3 基态修正模型 18
2.1.4 时空复合模型 19
2.1.5 离散格网单元列表模型 20
2.1.6 时空对象模型或双时间时空对象模型 21
2.1.7 基于特征的时空数据模型 21
2.1.8 图谱数据模型 21
2.1.9 面向对象的数据建模 22
2.1.10 基于事件的时空模型 23
2.1.11 基于时间语义模型或称时空属三域模型 24
2.1.12 基于状态事件的时空模型 25
2.2 并行模式 25
2.2.1 任务播种 26
2.2.2 单控制流多数据流 26
2.2.3 分治策略 26
2.2.4 数据流水线 27
2.2.5 投机策略 27
2.2.6 混合模型 27
2.3 时空模型与并行模式的特点与互补性 27
第3章 并行时空模型的概念与设计 29
3.1 时空中的并行模式 29
3.1.1 时空数据并行模式 29
3.1.2 时空任务并行模式 30
3.1.3 时空流水线并行模式 31
3.1.4 时空混合并行模式 32
3.1.5 时空并行模式的效率 34
3.2 并行时空模型中的基本概念 35
3.2.1 并行时空模型的组成要素 35
3.2.2 并行时空模型的定义 36
3.3 并行时空模型的设计 38
3.3.1 划分的原则 39
3.3.2 单级一维并行时空模型 40
3.3.3 单级二维并行时空模型 45
3.3.4 单级三维并行时空模型 49
3.3.5 多级并行时空模型 51
3.3.6 独立并行时空模型与关联并行时空模型 55
3.3.7 单式并行时空模型与复式并行时空模型 57
3.3.8 松耦合并行时空模型与紧耦合并行时空模型 61
3.4 并行时空模型举例 64
3.4.1 单级各维单式独立并行时空模型 64
3.4.2 复式联合多级并行时空模型 66
3.5 并行时空模型中的基本操作 66
3.5.1 并行本性聚类 67
3.5.2 并行查询 68
3.5.3 并行关系运算 70
3.5.4 并行时空分布 76
3.6 并行时空模型到并行计算机的映射方法 84
3.6.1 并行计算机的典型体系结构 84
3.6.2 映射的方法 85
第4章 并行时空模型的软件设计方法 87
4.1 时空构件 87
4.2 并行时空构件 89
4.2.1 并行时空构件的特点 89
4.2.2 并行时空构件的并行性 91
4.2.3 并行时空构件的分类 91
4.2.4 并行时空构件的设计 92
4.2.5 并行时空构件的开发原则 102
4.3 并行时空构件的数据传输模式 103
4.3.1 不同并行时空构件内存间传输模式 103
4.3.2 不同并行时空构件内外存间传输模式 104
4.3.3 不同并行时空构件外存间传输模式 105
4.3.4 不同传输模式的应用 105
4.4 并行时空构件的集成方法 106
4.4.1 1:1管道集成法 107
4.4.2 1:N管道集成法 107
4.4.3 单级总线集成法 108
4.4.4 多级总线集成法 109
第5章 传统时空模型到并行时空模型的升级 110
5.1 时空立方体模型的升级 110
5.1.1 串行时空立方体模型 110
5.1.2 划分串行时空立方体模型 111
5.1.3 索引时空立方体模型 111
5.1.4 并行时空立方体模型 112
5.1.5 多用户时空立方体模型 112
5.2 时空快照修正模型的升级 112
5.2.1 串行时空快照修正模型 112
5.2.2 划分时空快照修正模型 114
5.2.3 索引时空快照模型 114
5.2.4 并行时空快照模型 115
5.2.5 索引与并行时空2、4修正模型 115
5.2.6 改进后的索引与并行时空2、4修正模型 116
5.2.7 索引与并行时空3、5修正模型 116
5.2.8 改进后的索引与并行时空3、5修正模型 116
5.3 时空复合模型的升级 117
5.3.1 串行时空复合模型 117
5.3.2 划分时空复合模型 117
5.3.3 索引时空复合模型 118
5.3.4 并行时空复合模型 118
5.3.5 多用户时空复合模型 119
5.4 时空模型划分方法的比较 119
5.5 时空模型升级前后的性能比较 119
第6章 基于并行时空模型的数字城市并行化方法 122
6.1 数字城市的并行时空模型 122
6.1.1 数字城市中的时空数据来源 122
6.1.2 数字城市中的时空数据类型 123
6.1.3 数字城市的并行时空建模方法 124
6.1.4 数字城市并行时空建模的方法举例 129
6.2 利用并行时空模型升级已有数字城市的方法 130
6.2.1 升级程序结构 130
6.2.2 升级数据结构 131
6.2.3 升级数据库 132
6.2.4 升级显示机制 132
6.3 并行时空模型在数字城市中的使用方法 133
6.3.1 一种数字城市水平空间的三维重建方法 133
6.3.2 对数字城市三维空间的操作方法 135
6.3.3 数字城市在水平空间上的并行 137
6.3.4 数字城市在主题上的并行 140
6.3.5 数字城市在垂直空间上的并行 143
6.3.6 数字城市在时间维上的并行 146
6.3.7 数字城市中并行通信与协同 154
6.3.8 数字城市中识别和建模的并行 157
6.3.9 数字城市的多用户并行模式与并行显示 159
第7章 并行时空模型的应用方法 161
7.1 违章建筑监测 162
7.1.1 并行时空建模 162
7.1.2 并行时空模型中数据的组织与处理 163
7.1.3 并行数据操纵树状图 167
7.1.4 将并行时空模型映射到并行计算机 168
7.1.5 利用并行时空数据模型解决违章建筑问题的体系 168
7.2 实时交通监控 169
7.2.1 分析实时交通的时空并行性 169
7.2.2 实时交通监控的并行时空建模 170
7.2.3 并行时空模型中的同步机制 172
7.2.4 并行时空模型中数据的组织与处理 174
7.2.5 交通监控并行数据操作树状图 178
7.2.6 将并行时空模型映射到并行计算机 179
7.2.7 利用并行时空数据模型解决交通监控问题的体系 181
7.3 遥感图像识别 182
7.3.1 并行划分与建模 182
7.3.2 遥感图像识别的并行时空模型中对数据的操作方法 182
7.4 应用方法小结 183
7.4.1 应用的步骤 183
7.4.2 应用的关键 184
参考文献 185
索引 191
结束语 192
图1.1 房屋对象的分割与合并(石伟伟等,2006) 2
图1.2 欧洲数字城市(Ishida,2002) 8
图1.3 数字城市Kyoto(Ishida,2002) 9
图1.4 基于网格的区域划分(刘泓等,2006) 13
图2.1 时空立方体模型(翟亮等,2005) 17
图2.2 序列快照模型(翟亮等,2005) 18
图2.3 序列快照模型(姜晓轶和周云轩,2006) 18
图2.4 基态修正模型(翟亮等,2005) 19
图2.5 基态修正模型(姜晓轶和周云轩,2006) 19
图2.6 时空复合体模型(姜晓轶和周云轩,2006) 20
图2.7 时空复合模型(李阳东等,2008) 20
图2.8 离散格网单元列表模型(姜晓轶和周云轩,2006) 20
图2.9 时空对象(翟亮等,2005) 23
图2.10 基于事件的时空数据模型(姜晓轶和周云轩,2006) 24
图2.11 三域模型概念框架(李阳东等,2008) 24
图2.12 基于时间语义的模型(姜晓轶和周云轩,2006) 24
图2.13 时空状态事件描述(尹章才和李霖,2005) 25
图2.14 时空状态事件模型的组成(尹章才和李霖,2005) 25
图2.15 主从模式基本结构(何元清等,2002) 26
图2.16 单控制流多数据流结构(何元清等,2002) 26
图2.17 分治策略的虚拟树(何元清等,2002) 27
图2.18 数据流水线结构(何元清等,2002) 27
图3.1 时空单级数据并行模式 30
图3.2 时空多级数据并行模式 30
图3.3 时空单级任务并行模式 30
图3.4 时空多级任务并行模式 31
图3.5 时空单级流水线并行模式 31
图3.6 时空多级流水线并行模式 31
图3.7 时空数据-任务并行模式 32
图3.8 时空任务-数据并行模式 32
图3.9 时空流水-数据并行模式 33
图3.10 时空数据-流水并行模式 33
图3.11 时空流水-任务并行模式 34
图3.12 时空任务-流水并行模式 34
图3.13 传统时空模型与并行时空模型的关系 37
图3.14 时空模型按时空性进行分类 37
图3.15 并行时空模型按划分之间的并行性进行分类 38
图3.16 并行时空模型的分类 39
图3.17 基于时间维对应用对象集合进行划分 41
图3.18 基于时间维对用户对象集合进行划分 41
图3.19 基于时间维对观察对象集合进行划分 41
图3.20 基于空间维对应用对象集合进行划分 42
图3.21 基于空间维对用户对象集合进行划分 42
图3.22 基于空间维对观察对象集合进行划分 42
图3.23 基于本性维对应用对象集合进行划分 43
图3.24 基于本性维对用户对象集合进行划分 43
图3.25 基于本性维对观察对象集合进行划分 43
图3.26 基于本性维和时间维对对象集合进行划分 46
图3.27 基于空间维和时间维对对象集合进行划分 46
图3.28 基于空间维和本性维对对象集合进行划分 46
图3.29 基于空间维、本性维、时间维对对象集合进行划分 49
图3.30 多级划分 52
图3.31 单级时间维单式独立并行时空模型 64
图3.32 单级空间维单式独立并行时空模型 65
图3.33 单级主题维单式独立并行时空模型 65
图3.34 多级多式关联并行时空模型 66
图3.35 求同一个时间上的不同空间中的同类对象 67
图3.36 求同一个空间上的不同时间中的同类对象 67
图3.37 求不同时间上的不同空间中的同类对象 68
图3.38 在同一个时间上的不同空间中查询某对象或某些对象 69
图3.39 在同一个空间上的不同时间中查询某对象或某些对象 69
图3.40 在不同时间上的不同空间中查询某对象或某些对象 70
图3.41 同一时间不同空间内的对象之间的空间关系 70
图3.42 不同空间内的时间点对象之间的空间关系 71
图3.43 不同时间同一空间内的对象之间的空间关系 71
图3.44 不同时间不同空间内的对象之间的空间关系 72
图3.45 不同时间内的某对象自身与自身的空间关系 73
图3.46 不同时间内的各对象自身与自身的空间关系 73
图3.47 一段时间内的各对象轨迹之间的空间关系 74
图3.48 不同空间内的某类对象自身的时间轨迹之间的关系 74
图3.49 同一空间内不同时间点内对象之间的本性关系 75
图3.50 同一时间内不同空间内对象之间的本性关系 75
图3.51 不同时间内不同空间内对象之间的本性关系 76
图3.52 同一时间内某类对象的空间分布 77
图3.53 同一时间内多类对象的空间分布 77
图3.54 某类对象时间点的空间分布 78
图3.55 多类对象时间点的空间分布 78
图3.56 不同时间内某类对象的空间分布 79
图3.57 不同时间内多类对象的空间分布 80
图3.58 同一空间内某类对象的时间分布 81
图3.59 同一空间内多类对象的时间分布 81
图3.60 某类对象空间点的时间分布 82
图3.61 多类对象空间点的时间分布 82
图3.62 不同空间内某类对象的时间分布 83
图3.63 不同空间内多类对象的时间分布 84
图3.64 典型的并行计算机的体系结构 85
图3.65 映射图1 85
图3.66 映射图2 85
图3.67 映射图3 86
图3.68 映射图4 86
图4.1 并行时空模型的软件设计方法 87
图4.2 时空构件中的对象变量 88
图4.3 并行时空构件与并行时空模型的关系 90
图4.4 并行时空构件的金字塔结构 90
图4.5 划分数组 94
图4.6 主从式 96
图4.7 数组划分 100
图4.8 不同并行时空构件内存间传输模式 104
图4.9 不同并行时空构件内外存间传输模式 105
图4.10 不同并行时空构件外存间传输模式 105
图4.11 改进前的数据传输 106
图4.12 改进后的数据传输 106
图4.13 1:1管道集成法 107
图4.14 1:N管道集成法 108
图4.15 单级总线集成法 108
图4.16 多级总线集成法 109
图5.1 串行时空立方体模型(Langran,1992) 110
图5.2 划分串行时空立方体模型 111
图5.3 索引时空立方体模型 111
图5.4 并行时空立方体模型 112
图5.5 串行时空快照修正模型(Langran,1992) 113
图5.6 划分时空快照修正模型 114
图5.7 索引时空快照模型 115
图5.8 并行时空快照模型 115
图5.9 串行时空复合模型(Langran,1992) 117
图5.10 索引时空复合模型 118
图5.11 并行时空复合模型 118
图5.12 各类时空模型升级前后时空复杂度的比较 121
图6.1 数字城市的维度 124
图6.2 从空间维进行划分 125
图6.3 结合时间维和空间维进行划分 125
图6.4 结合三个维进行划分 125
图6.5 根据特征维的主题进行划分 126
图6.6 根据维的值进行自然划分 126
图6.7 根据维的值的数量划分 127
图6.8 根据空间内容的大小划分 127
图6.9 根据空间内容密度的间隔划分 127
图6.10 相对划分 128
图6.11 基于维刻度划分的时空建模 129
图6.12 基于维内容划分的时空建模 130
图6.13 基于维关系划分的时空建模 130
图6.14 升级数字城市的程序结构 131
图6.15 升级数字城市的数据结构 131
图6.16 升级数字城市的数据库 132
图6.17 数字城市的地表空间三维重建 134
图6.18 用于阴影监测的遥感图 134
图6.19 监测出的阴影图 135
图6.20 数字城市的地表空间三维重建 135
图6.21 选中建筑物显示高度和面积 136
图6.22 选中2个建筑物显示距离 136
图6.23 单个水平区域 137
图6.24 单个水平区域场景 138
图6.25 多个并行水平区域的空间关系 138
图6.26 多个并行水平区域场景 139
图6.27 数字城市在水平空间上的并行方法流程图 139
图6.28 数字城市的背景层 140
图6.29 数字城市的背景层+雾层 140
图6.30 数字城市的背景层+道路信息层 141
图6.31 数字城市的背景层+高程层 141
图6.32 数字城市的背景层+建筑层 141
图6.33 数字城市的背景层+车辆层 142
图6.34 数字城市的背景层+树木层 142
图6.35 数字城市的背景层+桥梁层 142
图6.36 数字城市的背景层+航空层 143
图6.37 数字城市在本性维上的并行方法流程图 143
图6.38 数字城市的空中部分 145
图6.39 数字城市的地表部分 145
图6.40 数字城市的地下部分 145
图6.41 数字城市在垂直空间上的并行方法流程图 146
图6.42 增量式更新方法 149
图6.43 同一地区不同年份的两幅不同源遥感影像 150
图6.44 时间1的数字城市 151
图6.45 时间2的数字城市 152
图6.46 时间3的数字城市 152
图6.47 时间4的数字城市 152
图6.48 三维城市中运动的车辆和飞机 154
图6.49 数字城市在时间维上的并行方法流程图 154
图6.50 同步起点 156
图6.51 同步过程 156
图6.52 同步终点 157
图6.53 数字城市中并行通信协同方法流程图 157
图6.54 数字城市中的任务并行方法流程图 158
图6.55 并行显示支持多用户使用 159
图6.56 数字城市在用户维上的并行方法流程图 160
图7.1 并行时空模型的应用机理 161
图7.2 违章建筑监测的并行时空模型 163
图7.3 违章监测并行数据操作树状图 167
图7.4 映射图1 168
图7.5 映射图2 168
图7.6 观察员集合的拓扑树 168
图7.7 利用并行时空模型解决违章建筑问题的总体结构 169
图7.8 实时交通监控的并行时空模型 171
图7.9 并行时空模型中同步机制示意图 174
图7.10 交通监控并行数据操作树状图 179
图7.11 映射图1 179
图7.12 映射图2 179
图7.13 映射图3 180
图7.14 映射图4 180
图7.15 映射图5 180
图7.16 映射图6 180
图7.17 观察拓扑图 181
图7.18 利用并行时空模型解决交通监测问题的总体结构 181
图7.19 并行计算机树状拓扑 183
表1.1 数字城市的已有技术 10
表5.1 各类时空模型特性比较表 120
表5.2 各类时空模型升级前后计算复杂度比较表 120
表5.3 各类时空模型升级前后存储复杂度比较表 121
表6.1 更新情况分类 150
表7.1 总表 163
表7.2 表名A 164
表7.3 表名B 164
表7.4 表名C 164
表7.5 表名A2007 164
表7.6 表名A2008 164
表7.7 表名B2007 164
表7.8 表名B2008 164
表7.9 表名C2007 165
表7.10 表名C2008 165
表7.11 表名A2007 165
表7.12 表名A2008 165
表7.13 表名B2007 165
表7.14 表名B2008 165
表7.15 表名C2007 165
表7.16 表名C2008 165
表7.17 表名1 172
表7.18 表名2 173
表7.19 表名3 173
表7.20 路段表 173
表7.21 路段1-时间1 174
表7.22 路段1-时间2 175
表7.23 路段2-时间1 175
表7.24 路段2-时间2 175
表7.25 数据字典 175
表7.26 时间点1 176
表7.27 时间点2 176
表7.28 时间点3 176
表7.29 时间点4 176
表7.30 时间点1 176
表7.31 连续时间点 177
表7.32 最拥挤路段 178
表7.33 最拥挤路段6 178
表7.34 最拥挤路段7 178
表7.35 最拥挤路段3 178
表7.36 最拥挤路段4 178