时空数据库查询与推理PDF电子书下载

第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