第1章 空间数据库概述 1
1.1 空间数据库基本功能 1
1.2 空间数据及空间对象 2
1.2.1 空间信息模型 2
1.2.2 空间数据类型 3
1.2.3 空间数据特征 4
1.2.4 空间数据结构 5
1.2.5 空间对象的特殊性 6
1.3 空间关系及表示 7
1.3.1 空间关系研究的意义 7
1.3.2 确定性空间拓扑关系及表示 7
1.3.3 不确定性空间拓扑关系及表示 13
1.3.4 确定性空间方向关系及表示 14
1.3.5 不确定性空间方向关系及表示 19
1.3.6 空间距离关系表示 19
1.4 空间数据查询 20
1.4.1 空间查询的基本操作类型 20
1.4.2 空间查询的基本具体类型 22
1.4.3 变体查询的具体类型 23
1.4.4 高维空间最近邻查询的具体类型 25
1.5 空间数据索引及查询处理 26
1.5.1 空间数据库索引技术 26
1.5.2 空间索引的基本思想 27
1.5.3 空间对象近似化 30
1.5.4 空间查询优化处理步骤 30
1.5.5 空间操作算法的性质和要求 31
1.6 空间关系推理 32
1.6.1 空间推理概述 32
1.6.2 空间关系推理类型 35
1.7 空间网络数据库概述 36
1.8 本章小结 37
第2章 空间数据库的基本索引结构 39
2.1 B－树及其变形树索引结构 39
2.1.1 B树索引结构 39
2.1.2 kd－树 41
2.1.3 K-D-B－树索引结构 42
2.1.4 B树索引结构 42
2.2 R－树索引结构 44
2.2.1 R－树索引结构 44
2.2.2 R树操作 46
2.3 R树和R树索引结构 48
2.3.1 R树索引结构 48
2.3.2 R树索引结构 49
2.4 QR－树 50
2.5 四叉树及四叉变形树索引结构 52
2.5.1 四叉树索引结构 52
2.5.2 变形四叉树索引结构 53
2.5.3 R－树索引和四叉树索引的比较 54
2.6 栅格文件索引结构 54
2.7 Voronoi图 56
2.7.1 Voronoi图的定义与性质 56
2.7.2 基于Voronoi图的邻近关系类型 59
2.7.3 Delaunay三角网的定义与性质 59
2.8 空间填充曲线 60
2.8.1 基于空间填充曲线的网格划分 62
2.8.2 Hilbert曲线的映射方法 62
2.8.3 Z曲线的映射方法 64
2.8.4 Gray曲线的映射方法 65
2.8.5 基于空间填充曲线索引结构 67
2.9 △-tree 68
2.9.1 主成分分析 68
2.9.2 △-tree 68
2.1 0本章小结 69
第3章 空间数据库的查询优化 71
3.1 空间数据库查询的优化技术概述 71
3.2 基于空间索引结点的优化 74
3.2.1 基于计算的索引结点的优化 75
3.2.2 MBR交叠区域计算 77
3.3 基于聚类分析的结点优化 79
3.3.1 结点的紧致结构 80
3.3.2 聚类结点MBR交叠的判定 81
3.3.3 DLSP判定算法实例分析 85
3.4 空间数据划分类索引的代价分析 86
3.4.1 基于R-树的空间选择与连接代价分析 87
3.4.2 基于QR－树的空间选择与连接代价分析 92
3.5 空间划分类索引的代价分析 96
3.5.1 空间划分类索引结构 97
3.5.2 动态更新的代价分析 98
3.5.3 索引动态更新代价模型 99
3.6 空间数据查询的其他优化技术 102
3.6.1 种子树连接模型 102
3.6.2 哈希分区连接模型 105
3.6.3 窗口缩减方法 107
3.6.4 空间连接索引技术 107
3.7 本章小结 108
第4章 空间数据库方向方位和连接查询 110
4.1 方向和方位上的运算 110
4.2 基于对象的方向方位模型设计 112
4.2.1 点对象的基于对象的方向模型 112
4.2.2 区域对象的基于对象方向方位的方向模型 114
4.2.3 开放区域的基于对象方向方位的方向模型 115
4.3 基于范围查询的对象方向方位的方向查询 118
4.3.1 基于范围查询策略的基本思想 118
4.3.2 基于范围查询策略的对象方向方位绝对方向查询算法 119
4.3.3 基于范围查询策略的对象方向方位方向查询算法 120
4.4 基于开放模型的对象方向方位的方向查询 122
4.4.1 基于开放模型查询策略的基本思想 122
4.4.2 基于开放模型策略的对象方向方位方向查询算法 122
4.5 本章小结 124
第5章 空间数据库最近邻查询 125
5.1 空间数据库最近邻查询概况 125
5.1.1 空间数据库最近邻查询的意义 125
5.1.2 空间数据库最近邻查询的研究现状 125
5.1.3 最近邻查询方法概论 126
5.2 基于R-树的顺序最近邻查询 127
5.2.1 最近邻查询的定义 127
5.2.2 最近邻查询的测量距离 128
5.2.3 深度优先遍历R－树的DF最近邻查询算法 131
5.2.4 宽度优先遍历R－树的BF最近邻查询算法 133
5.3 静态环境下基于V－树的最近邻查询 135
5.3.1 基于Voronoi图的V－树结构 135
5.3.2 基于Voronoi图的1NN查询 137
5.4 基于Voronoi图的kNN查询 138
5.5 静态环境下基于Voronci图的cNN查询 141
5.5.1 连续最近邻查询问题的定义和描述 142
5.5.2 基于Voronoi图的cNN查询算法 142
5.6 动态创建局部k阶Voronoi图的ckNN查询算法 144
5.7 空间最近对查询概述 146
5.7.1 空间最近对查询定义 146
5.7.2 空间最近对查询方法 147
5.8 空间强邻近对查询 148
5.8.1 空间强邻近对查询的相关理论 148
5.8.2 无障碍的强邻近对查询算法 150
5.9 本章小结 153
第6章 空间数据库反向最近邻查询 154
6.1 反向最近邻查询概述 154
6.1.1 问题产生背景 154
6.1.2 反向最近邻查询研究现状 155
6.2 反向最近邻查询的定义与性质 156
6.2.1 反向最近邻查询的定义 156
6.2.2 反向最近邻查询的性质 156
6.3 基于RNN－树的反向最近邻查询算法 158
6.4 基于RDNN－树的反向最近邻查询算法 162
6.5 基于Voronoi图的反向最近邻查询 164
6.6 Delaunay图的增量生成方法 165
6.6.1 基础定义与定理 166
6.6.2 Delaunay图的增量生成算法 166
6.7 基于Delaunay图的反向最近邻查询 168
6.7.1 Delanay树 168
6.7.2 基于Delaunay图的反向景近邻查询算法 169
6.8 基于Voronoi图的连续反向最近邻查询 172
6.8.1 基本理论 172
6.8.2 基于Voronoi图的连续单色反向最近邻查询 173
6.8.3 基于Voronoi图的连续双色反向最近邻查询算法 174
6.9 布尔范围查询和高维反向最近邻查询分析 176
6.9.1 布尔范围查询 176
6.9.2 高维反向最近邻查询分析 178
6.10 本章小结 179
第7章 空间数据库核心变体查询 181
7.1 障碍物群中最优有序路径的查询 181
7.1.1 基本定义 181
7.1.2 k完全相异可视最优有序路径查询 184
7.1.3 障碍空间k全局相异最优有序路径查询 190
7.2 空间障碍反向最近邻查询理论 194
7.2.1 可视性判断 194
7.2.2 障碍距离的计算 197
7.3 空间障碍反向最近邻查询 199
7.3.1 障碍反向最近邻查询定义 199
7.3.2 障碍反向最近邻查询点剪枝规则 199
7.3.3 障碍反向最近邻－过滤算法 200
7.3.4 障碍反向最近邻－精炼算法 202
7.3.5 障碍反向最近邻算法 203
7.4 有障碍的强邻近对查询算法 204
7.5 改进的有障碍强邻近对查询算法 206
7.6 本章小结 211
第8章 空间数据库一般变体查询 212
8.1 基于Voronoi图的组最近邻查询 212
8.1.1 基于Voronoi图的组最近邻查询基本理论 212
8.1.2 基于Voronoi图的组最近邻查询算法 216
8.2 范围约束的多类型最近邻查询 218
8.2.1 基本概念 218
8.2.2 满足范围约束条件的查询算法 219
8.2.3 单个数据集的处理算法 221
8.2.4 局部范围约束的多类型最近邻查询算法 222
8.2.5 Pcmt_NN算法的剪枝规则及分析 223
8.3 基于R－树的受约束空间连接查询算法 225
8.3.1 基于R树的受约束空间连接查询的直接方法 225
8.3.2 基于R－树的受约束空间连接查询算法 225
8.4 基于QR－树的受约束空间连接查询 227
8.4.1 基于QR－树的结点匹配算法 228
8.4.2 基于QR－树的受约束空间连接查询 229
8.5 基于Rav－树的索引结构及近似查询 233
8.5.1 VP区域分析 233
8.5.2 基于Rav－树的近似最近邻查询算法 234
8.5.3 基于Rav－树的分域查询算法 236
8.5.4 基于Rav－树的反向近似最近邻查询算法 237
8.6 反向最远邻的过滤与查询 238
8.6.1 查询点的RFN过滤判断 239
8.6.2 过滤后给定点的RFN查询 241
8.6.3 RFF查询及动态更新 243
8.7 动态数据集的反向最远邻 245
8.7.1 增加数据点的情况 245
8.7.2 减少数据点的情况 246
8.8 基于Voronoi图的有障碍道路网络最近邻查询 247
8.8.1 基于Voronoi网的有障碍的道路网络最近邻查询策略 247
8.8.2 基于Voronoi图的有障碍的道路网络最近邻查询算法 249
8.9 本章小结 250
第9章 线段的最近邻查询和反向最近邻查询 252
9.1 线段最近邻查询的基本理论 252
9.1.1 点与线段最近邻查询的相关定义 252
9.1.2 线段与线段不相交时的位置关系 254
9.1.3 基于两条线段不相交的有关定理 256
9.2 线段最近邻查询方法 258
9.2.1 R－树中MBR与线段的MBR的筛选规则 258
9.2.2 基于Mindist的筛选规则 259
9.2.3 判断线段与线段的位置关系的算法 259
9.2.4 线段与线段不相交时位置关系的确定算法 260
9.2.5 查询线段与被查询线段的最近距离的算法 260
9.2.6 查询线段在R－树中的遍历算法 261
9.3 基于Rcd－树的线段反向最近邻查询 262
9.3.1 平面线段反向最近邻的相关定义 262
9.3.2 基于Rcd－树的平面线段反向最近邻查询算法 263
9.4 基于Voronoi图的线段反向最近邻查询 265
9.4.1 线段Voronoi图的定义和性质 265
9.4.2 基于线段的反向最近邻 266
9.4.3 线段的查询区域 267
9.4.4 判断线段与查询区域相交的方法 268
9.4.5 Voronoi图的线段反向最近邻查询算法 268
9.5 基于Voronoi图的线段最近对查询 269
9.5.1 基于Voronoi图的线段最近对查询相关理论 270
9.5.2 基于Voronoi图的线段最近对查询算法 272
9.5.3 对数据集进行更新的处理 273
9.6 基于Vague集的平面线段不确定性区域 274
9.6.1 线段的模糊划分描述 274
9.6.2 平面线段的Vague区域描述 275
9.6.3 平面线段的Vague区域表示 276
9.6.4 平面线段的动态规律描述 277
9.7 平面动态线段的索引和查询 280
9.7.1 平面动态线段的索引 280
9.7.2 线段的近邻查询过程 281
9.8 本章小结 284
第10章 基于空间填充曲线的空间查询 285
10.1 基于空间填充曲线最近邻查询 285
10.2 高维空间基于Z曲线的近似k最近对查询 294
10.2.1 基本定义 294
10.2.2 高维空间基于Z曲线的近似k最近对查询算法 295
10.3 基于Hilbert曲线的高维k最近对查询 299
10.3.1 网格划分 299
10.3.2 基于Hilbert曲线的高维k最近对查询算法 302
10.4 基于Hilbert曲线的近似k最近邻查询 304
10.5 基于Z曲线的高维空间范围查询 306
10.5.1 网格划分 306
10.5.2 分割规则 308
10.5.3 Z曲线的高维空间范围查询算法 310
10.6 基于Bz树的高维空间范围查询 312
10.6.1 Bz树索引结构 312
10.6.2 Bz树上的操作 313
10.6.3 Bz树高维空间范围查询算法 314
10.7 基于Hilbert曲线网格划分聚类 315
10.7.1 聚类 316
10.7.2 基于Hilbert曲线网格划分聚类算法 317
10.8 本章小结 324
第11章 基于主存△-tree的高维数据查询 326
11.1 高维主存kNN连接索引结构的基础算法 326
11.1.1 △-tree R的基础算法R_insertR 327
11.1.2 构建△-tree R和△-tree S算法 330
11.1.3 △-tree S的基础算法R_insertS 330
11.1.4 相关性质及定义 332
11.2 自底向上深度递归kNN查询 333
11.2.1 理论基础 333
11.2.2 相关子算法 335
11.2.3 BU_DF_knn_Search算法 338
11.3 自顶向下主存△-tree的高维数据相似连接 339
11.3.1 理论基础 340
11.3.2 自顶向下主存△-tree的高维数据相似连接算法 342
11.4 改进的基于△-tree R的kNN连接 345
11.4.1 基于△-tree R的kNN连接算法及其子算法 345
11.4.2 改进的基于△-tree R的kNN连接算法 350
11.5 基于△-Rdnn-tree的自连接 351
11.5.1 反向k最近邻索引结构△-Rdnn-tree 351
11.5.2 基于△-Rdknn-tree的kNN 自连接算法 353
11.6 基于△-Rdnn-tree的反向k最近邻连接 355
11.7 基于△-Rdnn-tree的反向k最近邻查询 357
11.8 本章小结 359
第12章 空间网络间的空间关系及推理 360
12.1 空间网络间的空间关系表示 360
12.1.1 基本概念 360
12.1.2 严格型的空间网络间的空间关系表示 362
12.1.3 扩展型的空间网络间的空间关系表示 364
12.2 空间网络间的空间关系的交集模型 367
12.2.1 空间网络间的空间关系的交集模型表示 367
12.2.2 空间网络间的空间关系的特征条件式和蕴涵条件式 369
12.3 空间网络间的空间关系推理 377
12.4 实例分析 379
12.5 本章小结 382
第13章 空间方向关系的关系推理基础 383
13.1 基于MBR的主方向关系的反关系推理 383
13.1.1 二维空间主方向关系 383
13.1.2 基于MBR的主方向关系的反关系推理 385
13.2 区域对象间主方向关系的反关系推理 386
13.2.1 矩形主方向关系的原关系 386
13.2.2 主方向关系的反关系推理算法 388
13.2.3 算法验证 390
13.3 三维空间方向关系的表达与推理 391
13.3.1 三维空间主方向关系模型 391
13.3.2 三维空间方向关系推理 394
13.4 本章小结 403
参考文献 405