第1章 预备知识 1
1.1 时空数据库概述 1
1.1.1 空间数据库基本功能与分类 1
1.1.2 空间数据类型 2
1.1.3 空间数据结构 3
1.1.4 空间数据特征 4
1.1.5 空间对象具有的特殊性 5
1.2 空间数据存储和查询 6
1.2.1 空间数据存储 6
1.2.2 空间查询 7
1.2.3 空间对象近似化 9
1.2.4 空间查询处理步骤 9
1.3 空间数据库索引 11
1.3.1 空间数据库索引技术概述 11
1.3.2 B-树和B+树索引结构 11
1.3.3 R-树索引结构 13
1.3.4 R-树操作 15
1.3.5 R＊树 21
1.3.6 四叉树及其变形树 22
1.4 本章小结 23
第2章 空间数据库最近邻查询 24
2.1 空间数据库最近邻查询概况 24
2.1.1 空间数据库最近邻查询的意义 24
2.1.2 空间数据库最近邻查询的研究现状 25
2.1.3 最近邻查询方法概论 26
2.2 顺序最近邻查询 27
2.2.1 最近邻查询的定义 27
2.2.2 最近邻查询的测量距离 28
2.2.3 基于R-树的最近邻顺序查询算法 31
2.3 Voronoi图及生成方法 32
2.3.1 Voronoi图的定义与性质 33
2.3.2 基于Voronoi图的邻近关系类型 35
2.3.3 Delaunay三角网的定义与性质 35
2.4 静态环境下基于V-树的NN查询 37
2.4.1 基于Voronoi图的V-树结构 37
2.4.2 基于Voronoi图的1NN查询 40
2.5 基于Voronoi图的kNN查询 41
2.6 静态环境下基于Voronoi图的cNN查询 44
2.6.1 连续最近邻查询问题的定义和描述 45
2.6.2 基于Voronoi图的cNN查询算法 45
2.7 动态创建局部k阶Voronoi图的连续ckNN查询算法 47
2.8 本章小结 50
第3章 反向最近邻查询 52
3.1 反向最近邻查询概述 52
3.1.1 问题产生背景 52
3.1.2 反向最近邻查询研究现状 53
3.2 反向最近邻查询的定义与性质 54
3.2.1 反向最近邻查询定义 54
3.2.2 反向最近邻查询的性质 54
3.3 基于RNN-树的反向最近邻查询算法 57
3.4 基于RDNN-树的反向最近邻查询算法 60
3.5 Delaunay图的增量生成方法 63
3.5.1 基础定义与定理 63
3.5.2 Delaunay图的增量生成算法 64
3.6 基于Delaunay图的反向最近邻查询 66
3.6.1 Delaunay树 66
3.6.2 基于Delaunay图的反向最近邻查询算法 66
3.7 本章小结 70
第4章 基于Voronoi图的组和多类型最近邻查询 71
4.1 基本定义与定理 71
4.2 基于Voronoi图的组最近邻查询 75
4.3 局部范围约束的多类型最近邻查询 77
4.3.1 基本概念 78
4.3.2 满足范围约束条件的查询算法 79
4.3.3 单个数据集的处理算法 81
4.3.4 局部范围约束的多类型最近邻查询算法 82
4.3.5 Pcmt_NN算法的剪枝策略及分析 83
4.4 障碍物群中最优有序路径的查询 85
4.4.1 基本定义 85
4.4.2 k完全相异可视最优有序路径查询 89
4.4.3 障碍空间k全局相异最优有序路径查询 94
4.5 本章小结 98
第5章 线段的最近邻查询 100
5.1 线段最近邻查询的基本理论 100
5.1.1 点与线段最近邻查询的相关定义 100
5.1.2 线段与线段不相交时的位置关系 103
5.1.3 基于两条线段不相交的有关定理 105
5.2 线段最近邻查询方法 108
5.2.1 R-树中MBR与线段的MBR的筛选规则 108
5.2.2 基于Mindist的筛选规则 108
5.2.3 判断线段与线段的位置关系的算法 109
5.2.4 线段与线段不相交时位置关系的确定算法 110
5.2.5 查询线段与被查询线段的最近距离的算法 110
5.2.6 查询线段在R-树中的遍历算法 111
5.3 基于线段索引树SI-树的平面线段集最近邻查询 112
5.3.1 线段索引树SI-树 112
5.3.2 线段索引树的生成 114
5.3.3 线段集的最近邻查询的剪枝规则 115
5.3.4 基于SI-树的最近邻查询算法 116
5.4 线段的反向最近邻查询 119
5.4.1 平面线段反向最近邻的相关定义 119
5.4.2 基于Rcd-树的平面线段反向最近邻查询算法 120
5.5 本章小结 122
第6章 基于空间填充曲线的空间查询 124
6.1 基于空间填充曲线网格划分最近邻查询 125
6.1.1 Hilbert曲线的映射方法 126
6.1.2 Z曲线的映射方法 128
6.1.3 Gray曲线的映射方法 129
6.1.4 基于空间填充曲线索引结构 131
6.2 基于空间填充曲线最近邻查询 132
6.3 高维空间基于Z曲线的近似k最近对查询 143
6.3.1 基本定义 143
6.3.2 高维空间基于Z曲线的近似k最近对查询算法 145
6.3.3 误差分析 147
6.4 基于Hilbert曲线的高维k最近对查询 148
6.4.1 网格划分 149
6.4.2 基于Hilbert曲线的高维k最近对查询 151
6.5 基于Hilbert曲线的近似k最近邻查询 154
6.6 基于Z曲线高维空间范围查询 156
6.6.1 网格划分 156
6.6.2 分割规则 159
6.6.3 Z曲线的高维空间范围查询算法 162
6.7 基于Bz树高维空间范围查询 163
6.7.1 Bz树索引结构 164
6.7.2 Bz树上的操作 165
6.7.3 Bz树高维空间范围查询算法 166
6.8 基于Hilbert曲线网格划分聚类 167
6.8.1 聚类 168
6.8.2 基于Hilbert曲线网格划分聚类算法 169
6.9 本章小结 178
第7章 曲面最近邻及反向最远邻查询 180
7.1 柱面及锥面上的点最近邻查询 180
7.2 球面上的点的最近邻查询 182
7.2.1 利用球面Voronoi图计算最近邻 182
7.2.2 利用欧式空间内的空间数据索引结构 183
7.2.3 降维方法 183
7.2.4 曲面投影于平面 187
7.3 反向最远邻的过滤与查询 189
7.3.1 查询点的RFN过滤判断 190
7.3.2 过滤后给定点的RFN的查询 192
7.3.3 RFF查询及动态更新 194
7.4 动态数据集的反向最远邻 196
7.4.1 增加数据点的情况 196
7.4.2 减少数据点的情况 197
7.5 本章小结 198
第8章 基于主存△-tree的高维空间连接 200
8.1 理论基础 200
8.1.1 主成分分析 200
8.1.2 △-tree 201
8.2 基于主存△-tree的高维数据自相似连接算法 202
8.3 基于主存△-tree的高维空间相似连接处理 210
8.3.1 基于主存△-tree的相似连接索引结构 210
8.3.2 基于主存△-tree的相似连接算法 214
8.4 基于主存△-tree的高维空间kNN连接处理 216
8.4.1 基于主存△-tree的kNN连接索引结构 216
8.4.2 基于主存△-tree的kNN连接算法 222
8.5 本章小结 229
第9章 时空数据库最近邻查询 230
9.1 时空移动对象概述 230
9.1.1 移动对象的描述 230
9.1.2 移动对象环境的特点 231
9.1.3 移动对象数据的空间属性 231
9.1.4 移动对象的位置的表示 232
9.1.5 对象位置不确定性的表示与处理 232
9.2 时空数据库索引技术 233
9.2.1 移动对象索引技术 233
9.2.2 时空数据库索引技术要求 234
9.2.3 TPR-树时空索引结构 235
9.2.4 TPR＊树 238
9.3 基于TPR-树的时间段最近邻查询 239
9.3.1 基于TPR-树的时间段最近邻查询 240
9.3.2 基于分界时间的TPR-树最近邻查询算法 242
9.4 移动对象的连续k最优有序路径查询 244
9.4.1 基本概念 244
9.4.2 移动对象的连续k最优有序路径查询 246
9.4.3 静态全局算法 247
9.4.4 动态局部算法 248
9.5 移动对象动态反向最近邻查询 251
9.5.1 基本定义与定理 251
9.5.2 利用时空距离函数计算移动对象q的动态最近邻 253
9.5.3 利用时空距离函数及限界区域查询q的动态反向最近邻 256
9.5.4 时空索引结构 259
9.5.5 时间段里q的动态反向最近邻查询算法 260
9.6 本章小结 262
第10章 时空道路网络中最近邻查询 264
10.1 启发式计算时空道路网络的最近邻查询理论基础 264
10.1.1 查询模式分析 265
10.1.2 选择移动查询点的最近邻启发式规则 266
10.1.3 P区域和R区域 266
10.1.4 道路网络的划分和边界点的选择 269
10.2 启发式时空道路网络中的最近邻查询 269
10.2.1 启发式时空道路网络中的最近邻查询算法 269
10.2.2 启发式时空道路网络中的连续最近邻查询算法 271
10.3 时空道路网络中移动对象的连续最近邻查询 272
10.3.1 基本定义和定理 272
10.3.2 cNN查询算法 275
10.3.3 实例分析 279
10.4 网络环境下移动对象的不确定性最近邻查询 281
10.4.1 移动对象的不确定性轨迹模型 281
10.4.2 相关概念 282
10.4.3 道路网络中移动对象的概率近邻查询过程 285
10.4.4 概率计算 289
10.5 本章小结 294
第11章 移动对象的轨迹查询 296
11.1 移动对象轨迹的描述 296
11.1.1 插值方法 296
11.1.2 插值方法描述轨迹 297
11.1.3 道路网络轨迹的插值方法 301
11.1.4 线性函数表示方法 302
11.2 移动对象的不确定轨迹和查询 302
11.2.1 时间不确定性 302
11.2.2 空间不确定性 303
11.2.3 时空不确定性 303
11.2.4 轨迹的不确定查询 305
11.2.5 移动对象轨迹的更新策略 308
11.3 移动对象过去轨迹查询 308
11.3.1 轨迹更新索引 309
11.3.2 原四叉树索引存在的不足 311
11.3.3 将来轨迹FT-四叉树 312
11.3.4 更新算法 313
11.3.5 基于FT-四叉树的高维空间查询 315
11.4 网络中移动对象轨迹查询 316
11.4.1 网络模型 317
11.4.2 索引结构 319
11.4.3 插入算法 319
11.4.4 移动插入算法 320
11.4.5 查询算法 321
11.5 本章小结 323
第12章 主方向关系网络一致性检验和组合推理 325
12.1 空间推理概述 325
12.1.1 空间关系研究的意义 325
12.1.2 空间推理类型 325
12.1.3 定性空间推理 326
12.2 空间方向关系模型和区间代数 328
12.2.1 定量的方向关系模型 328
12.2.2 定性的方向模型 329
12.2.3 区间代数中的凸关系 329
12.2.4 矩形关系网络 330
12.3 基于MBR的主方向关系模型 331
12.3.1 最小矩形边界框MBR的定义 331
12.3.2 矩形代数与主方向的关系 334
12.3.3 矩形代数的基本运算 336
12.3.4 基于MBR主方向关系运算 337
12.4 主方向关系网络一致性 339
12.4.1 一致性检验问题 339
12.4.2 点物体的空间主方向表示及代数运算 340
12.5 基于MBR的主方向关系的一致性检验算法 342
12.5.1 主方向关系的子类 342
12.5.2 一致性检测 343
12.5.3 基于MBR主方向关系上的可达类 344
12.5.4 基于MBR的主方向关系的一致性检验算法 346
12.6 基于矩阵的方向关系组合推理 348
12.6.1 基本概念 349
12.6.2 方向关系矩阵间的运算 351
12.6.3 方向关系矩阵间组合 352
12.6.4 原子方向关系矩阵间的组合推理规则 354
12.7 原子方向关系与基本方向关系的组合 356
12.8 基本方向关系矩阵之间的组合 359
12.9 本章小结 361
第13章 Vague区域关系推理 363
13.1 不确定的区域关系 363
13.1.1 空间关系概述 363
13.1.2 确定性空间区域关系 363
13.1.3 不确定性空间区域关系 364
13.2 Vague集和Vague区域 366
13.2.1 Vague集的定义与性质 368
13.2.2 Vague区域的定义 368
13.3 无核Vague区域关系 371
13.3.1 无核Vague区域的描述与划分 371
13.3.2 同一平面中的无核Vague区域关系 373
13.3.3 不同平面中的无核Vague区域关系 376
13.3.4 两类空间关系的旋转对应关系 377
13.3.5 实例分析 377
13.4 同一平面中的含核Vague区域关系 381
13.4.1 含核Vague区域的描述与划分 381
13.4.2 同一平面中的含核Vague区域关系 383
13.4.3 蕴涵定理和算法 388
13.4.4 实例分析 390
13.5 不同平面中的含核Vague区域关系 395
13.5.1 DPVR关系交集模型 396
13.5.2 DPVR关系和CPVR关系的旋转对应关系 398
13.5.3 实例分析 400
13.6 含洞Vague区域关系 402
13.6.1 含洞Vague区域基本概念 404
13.6.2 Vague洞区域关系 405
13.6.3 凸壳化洞区域关系 408
13.6.4 含洞不规则Vague区域关系 410
13.6.5 实例分析 411
13.7 多范畴的Vague区域关系 415
13.7.1 多类粗糙Vague区域关系表示 415
13.7.2 粗糙Vague区域关系的可能蕴涵式 419
13.7.3 Vague区域关系的相互转化及关联性 421
13.8 本章小结 422
第14章 Vague区域关系组合推理 423
14.1 Vague区域关系和Vague方向关系组合推理 423
14.1.1 Vague方向关系表示 424
14.1.2 Vague方向关系的动态邻接关系 427
14.1.3 Vague方向关系和区域关系的复合关联推理 428
14.1.4 实例分析 429
14.2 Vague区域关系和Vague时间关系组合分析 432
14.2.1 Vague时间段关系 432
14.2.2 线性Vague时间段关系 433
14.2.3 周期性双向叠合时间段关系 438
14.2.4 Vague时间段关系和Vague区域关系的复合推理 441
14.2.5 实例分析 442
14.3 本章小结 445
参考文献 447