动态环境下移动对象连续最近邻查询研究

论文摘要

随着科学技术的快速发展,卫星全球定位系统和无线通讯技术已经能够跟踪并记录移动对象的位置。同时,移动对象的连续运动也对数据库技术提出了新的要求和挑战,能够描述移动对象及其位置信息的移动对象数据库应运而生。在移动对象数据库中,移动对象的最近邻查询问题一直是其中的研究热点。然而,过去的研究工作大部分都集中于静态环境下的最近邻查询,如何将静态环境下的最近邻查询方法扩展到动态环境下成为研究中的重点和难点。本文对动态环境下的最近邻查询方法进行了研究,提出了以TPR树为索引结构、引入分界时间的最近邻查询算法,并将这种算法扩展到了动态环境下的k个连续最近邻查询。首先通过对移动对象索引技术的分析与比较,详细研究了一种适合于进行未来最近邻查询、可以提高查询的质量和效率的索引方法:TPR树,并在这一索引结构的基础上进行查询算法的研究。其次通过对最近邻查询问题的特征分析,提出了一种通过计算分界时间完成动态环境下最近邻查询的解决方案,并给出了分界时间的计算公式和方法。与此同时,将一种近似计算距离的算法进行改进,提出了能够精确计算距离的算法。然后将现有的静态环境下的最近邻查询算法与本文提出的分界时间相结合,提出了两种分别通过深度和宽度优先遍历TPR树利用剪枝技术找到移动对象最近邻的查询算法,不但适用于高维空间而且具有很强的扩展性。最后进一步将这两种算法扩展到动态环境下的k个最近邻查询和连续最近邻查询,并通过实验验证了算法的可行性和正确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究目的及意义
• 1.2 移动对象数据库的发展状况
• 1.3 索引技术的研究现状
• 1.3.1 空间索引技术
• 1.3.2 移动对象索引技术
• 1.4 最近邻查询方法的研究现状
• 1.4.1 静态环境下的最近邻查询
• 1.4.2 动态环境下的最近邻查询
• 1.5 课题来源及研究内容
• 1.6 论文结构安排
• 第2章 基础理论
• 2.1 空间数据库索引技术
• 2.1.1 R 树索引结构
• 2.1.2 R 树操作
• 2.2 移动对象数据库索引技术
• 2.2.1 移动对象索引技术分析
• 2.2.2 TPR 树索引结构
• 2.2.3 TPR 树与R 树的比较
• 2.3 静态环境下的最近邻查询算法
• 2.3.1 最近邻查询的测量距离
• 2.3.2 DF 算法概述
• 2.3.3 BF 算法概述
• 2.4 本章小结
• 第3章 分界时间计算方法
• 3.1 最近邻查询问题特征分析
• 3.2 分界时间的定义
• 3.3 静态环境下分界时间的计算
• 3.4 动态境下移动对象分界时间的计算
• 3.5 动态环境下包含矩形分界时间的计算
• 3.5.1 计算公式
• 3.5.2 近似的距离计算算法
• 3.5.3 改进的距离计算算法
• 3.5.4 计算结果
• 3.6 本章小结
• 第4章 引入分界时间的最近邻查询算法
• 4.1 基于R 树的DF 算法
• 4.2 基于R 树的BF 算法
• 4.3 基于TPR 树的段时间最近邻查询算法
• 4.3.1 问题描述
• 4.3.2 查询算法
• 4.4 引入分界时间的最近邻查询算法
• 4.4.1 算法描述
• 4.4.2 引入分界时间的DF 扩展算法
• 4.4.3 引入分界时间的BF 扩展算法
• 4.4.4 算法分析与比较
• 4.5 本章小结
• 第5章 最近邻查询算法的扩展及实验研究
• 5.1 K 个近邻查询
• 5.1.1 静态环境下的K 个近邻查询
• 5.1.2 K 个近邻查询中分界时间的定义及计算方法
• 5.1.3 引入分界时间的K 个近邻查询
• 5.2 连续最近邻查询
• 5.2.1 静态环境下的连续最近邻查询
• 5.2.2 引入分界时间的连续最近邻查询
• 5.3 实验研究
• 5.3.1 实验设计
• 5.3.2 K 近邻查询性能
• 5.3.3 实验结论
• 5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢