时空数据库查询处理关键技术研究

论文摘要

移动计算、无线通信以及定位技术的快速发展使得对各种空间与时空对象的存储和管理成为了现实需求。大量的应用领域(如地理信息系统、智能导航、交通管制、天气预报、军事、移动电子商务等)均迫切需要有效地查询这些数据对象。然而,空间与时空数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用,需要研究新的查询处理技术。因此,如何提供各种高效的空间与时空对象查询处理技术是当前时空数据库领域的研究热点之一。时空数据库的查询效率是衡量时空数据库性能的重要指标。尽管已有许多的研究学者致力于这方面的研究,并取得了许多可喜的成果,但距离满足用户不断出现的、复杂而多样的查询要求还有一定的差距,仍有待相关研究进一步的深入。此外,国内开展该领域研究的单位还不多,在该领域的研究水平和国外相比,还存在着一定的差距。因而,适时开展时空数据库查询处理技术的研究是必需的,有着重要的学术价值和广阔的应用前景。鉴于此,本文从两个方面对时空数据库查询处理中的关键技术问题进行了研究和探索。一是如何有效地处理针对空间对象的各类查询,在这方面,本文主要探讨了并行最近邻查询、并行Skyline查询、分支界限Skyline查询以及相互(即对称)最近邻查询的处理技术;二是如何有效地处理针对历史移动对象轨迹(即时空对象)的各类查询,在这方面,本文重点讨论了k(≥1)最近邻(kNN)查询、历史连续kNN(HCkNN)查询、受限kNN(CkNN)查询、历史连续CkNN(HCCkNN)查询、相互最近邻(MNN)查询以及历史连续MNN(HCMNN)查询的处理技术。本文的主要贡献和创新可概括如下;1)首次提出了多磁盘环境下基于最佳优先的并行k(≥1)最近邻查询算法。这些算法在效率和可扩展性方面的性能均大大地优于现有的同类算法。2)首次给出了多磁盘环境下的并行Skyline查询处理方法,并用实验对其性能进行了全面地评价和分析。3)提出了一种存储最佳的分支界限Skyline查询算法。该算法既有最佳的I/O代价(即结点访问量)和较低的CPU开销,又有最少的内存空间耗费,并在性能上明显地好于目前最好的同类算法。4)探讨了历史移动对象轨迹的kNN查询和HCkNN查询的问题。遵循最佳优先搜索范例,分别提出了关于静态查询点和移动查询轨迹的kNN查找和HCkNN查找的处理方法。这些方法在效率和可扩展性方面的性能远远地胜过已有的同类算法。此外,引入了一个新颖的距离度量标准,开发了若干个剪枝启发式,设计了用于存放HCkNN查询结果的k个最近列表的更新方法。5)首次引入并解决了空间对象的MNN查询问题。形式化定义了这一新颖的MNN查询类型,并分析其特性;提出了一系列的MNN查询算法,并通过实验评估其性能。6)首次引入并讨论了历史移动对象轨迹的CkNN查询和HCCkNN查询的问题。形式化定义了这些新的查询类型,分别提出了若干针对静态查询点和移动查询轨迹的CkNN查找和HCCkNN查找的处理方法,并对这些方法进行了全面的性能评价和分析比较。7)首次引入并研究了历史移动对象轨迹的MNN查询和HCMNN查询的问题。形式化定义了这些新颖的查询类型,分别提出了关于静态查询点和移动查询轨迹的MNN查找和HCMNN查找的处理方法,并对这些方法的性能进行了系统的实验评估。本文在空间与时空对象查询处理技术方面所取得的研究成果不仅丰富了我国在时空数据库查询处理技术方面的理论宝库,而且在一定程度上推动了时空数据库的实用化进程。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状及分析
• 1.2.1 空间查询处理
• 1.2.1.1 最近邻查询
• 1.2.1.2 反最近邻查询
• 1.2.1.3 空间连接查询
• 1.2.1.4 最近对查询
• 1.2.1.5 Skyline查询
• 1.2.2 历史移动对象轨迹查询处理
• 1.2.2.1 区域查询
• 1.2.2.2 基于轨迹查询
• 1.2.2.3 k（≥1）最近邻查询
• 1.2.2.4 相似轨迹查询
• 1.2.2.5 不确定轨迹查询
• 1.3 存在的问题
• 1.4 本文研究目标和研究内容
• 1.4.1 研究目标
• 1.4.2 研究内容
• 1.5 本文结构组织
• 1.6 几个缩写的说明
• 第二章 基于最佳优先的并行最近邻查询
• 2.1 引言
• 2.2 定义和问题特性
• 2.3 并行的最近邻查询算法
• 2.3.1 剪枝策略
• 2.3.2 算法描述
• 2.3.3 算法示例
• 2.3.4 算法分析
• 2.4 并行的k最近邻查询算法
• 2.4.1 剪枝策略
• 2.4.2 算法描述
• 2.4.3 算法示例
• 2.4.4 算法分析
• 2.5 实验评估
• 2.5.1 实验设置
• 2.5.2 并行的最近邻查询算法实验结果
• 2.5.3 并行的k最近邻查询算法实验结果
• 2.6 本章小结
• 第三章 基于多磁盘环境的并行Skyline查询
• 3.1 引言
• 3.2 基本的并行Skyline查询算法
• 3.2.1 算法描述
• 3.2.2 算法分析
• 3.3 改进的并行Skyline查询算法
• 3.3.1 基于支配检查的剪枝策略
• 3.3.2 算法描述
• 3.3.3 算法分析
• 3.4 实验评估
• 3.4.1 实验设置
• 3.4.2 实验结果
• 3.5 本章小结
• 第四章 存储最佳的分支界限Skyline查询
• 4.1 引言
• 4.2 分支界限Skyline查询算法
• 4.3 基于支配检查的剪枝策略
• 4.4 改良的分支界限Skyline查询算法
• 4.4.1 算法描述
• 4.4.2 算法分析
• 4.5 实验评估
• 4.5.1 实验设置
• 4.5.2 实验结果
• 4.6 本章小结
• 第五章 历史移动对象轨迹的kNN和HCkNN查询
• 5.1 引言
• 5.2 距离度量
• 5.3 剪枝策略
• 5.4 点的k最近邻查询算法
• 5.4.1 算法描述
• 5.4.2 算法分析
• 5.5 轨迹的k最近邻查询算法
• 5.5.1 算法描述
• 5.5.2 算法分析
• 5.6 k最近列表的更新
• 5.7 点的历史连续k最近邻查询算法
• 5.8 轨迹的历史连续k最近邻查询算法
• 5.9 实验评估
• 5.9.1 实验设置
• 5.9.2 距离度量的计算方法实验结果
• 5.9.3 点的k最近邻查询算法实验结果
• 5.9.4 轨迹的k最近邻查询算法实验结果
• 5.9.5 点的历史连续k最近邻查询算法实验结果
• 5.9.6 轨迹的历史连续k最近邻查询算法实验结果
• 5.10 本章小结
• 第六章 相互的最近邻查询
• 6.1 引言
• 6.2 问题陈述
• 6.2.1 相互的最近邻查询定义
• 6.2.2 相互的最近邻查询特性
• 6.3 基本算法
• 6.3.1 算法描述
• 6.3.2 算法分析
• 6.4 改进算法
• 6.4.1 利用批量区域查询算法
• 6.4.2 利用批量最近邻查询算法
• 6.4.3 利用带有剪枝的最近邻查询算法
• 6.4.4 利用带有剪枝的反最近邻查询算法
• 6.5 实验评估
• 6.5.1 实验设置
• 6.5.2 实验结果
• 6.6 本章小结
• 第七章 历史移动对象轨迹的CkNN和HCCkNN查询
• 7.1 引言
• 7.2 问题陈述
• 7.3 点的受限k最近邻查询算法
• 7.3.1 两步骤算法
• 7.3.2 基于深度优先算法
• 7.3.3 基于最佳优先算法
• 7.4 轨迹的受限k最近邻查询算法
• 7.4.1 基于深度优先算法
• 7.4.2 基于最佳优先算法
• 7.5 点的历史连续受限k最近邻查询算法
• 7.5.1 基于深度优先算法
• 7.5.2 基于最佳优先算法
• 7.6 轨迹的历史连续受限k最近邻查询算法
• 7.6.1 基于深度优先算法
• 7.6.2 基于最佳优先算法
• 7.7 实验评估
• 7.7.1 实验设置
• 7.7.2 点的受限k最近邻查询算法实验结果
• 7.7.3 轨迹的受限k最近邻查询算法实验结果
• 7.7.4 点的历史连续受限k最近邻查询算法实验结果
• 7.7.5 轨迹的历史连续受限k最近邻查询算法实验结果
• 7.8 本章小结
• 第八章 历史移动对象轨迹的MNN和HCMNN查询
• 8.1 引言
• 8.2 问题陈述
• 8.3 点的相互最近邻查询算法
• 8.3.1 简单算法
• 8.3.2 重用一个堆算法
• 8.3.3 重用两个堆算法
• 8.3.4 带有剪枝的重用两个堆算法
• 8.4 轨迹的相互最近邻查询算法
• 8.5 点的历史连续相互最近邻查询算法
• 8.5.1 简单算法
• 8.5.2 带有剪枝的重用两个堆算法
• 8.6 轨迹的历史连续相互最近邻查询算法
• 8.7 实验评估
• 8.7.1 实验设置
• 8.7.2 点的相互最近邻查询算法实验结果
• 8.7.3 轨迹的相互最近邻查询算法实验结果
• 8.7.4 点的历史连续相互最近邻查询算法实验结果
• 8.7.5 轨迹的历史连续相互最近邻查询算法实验结果
• 8.8 本章小结
• 第九章 总结与展望
• 9.1 本文完成的主要研究工作及成果
• 9.2 本文主要的创新点
• 9.3 进一步的研究工作
• 参考文献
• 攻读博士学位期间发表的论文
• 致谢