移动对象的动态反向最近邻的研究

论文摘要

空间数据库是近年新的研究领域,是一门前沿的交叉学科,它在地理信息系统、计算机辅助设计CAD、多媒体信息系统MMIS以及数据仓库DWH技术等诸多应用领域中都有着广泛的应用。反向最近邻查询是空间数据库中最重要的算法之一,是在最近邻查询的基础上提出的一种新的查询类型。传统的反向最近邻查询方法主要是静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点,传统的反向最近邻查询算法不能满足移动对象的查询请求。本课题在研究目前多种反向最近邻查询技术的基础上,提出了一种解决移动对象动态反向最近邻的查询方法。将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将现有半平面修剪策略进行了改进,给出了移动对象的动态反向最近邻的查询方案,对算法的可终止性、正确性和时间复杂性进行了分析,并用实例进行了验证。同时将移动对象的动态反向最近邻查询技术扩展到移动对象的动态反向k最近邻的查询,并给出了移动对象的动态反向k最近邻的查询方案及相关证明。本课题提出的查询技术能够高效地处理查询点和查询点集为动态的情况,对移动对象的动态反向最近邻的查询技术的发展有重要意义。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.3 课题来源及主要研究内容
• 1.3.1 课题来源
• 1.3.2 主要研究内容
• 第2章 空间数据库关键技术
• 2.1 空间数据和空间数据库
• 2.1.1 空间对象
• 2.1.2 空间数据特征
• 2.1.3 空间数据模型
• 2.1.4 空间数据库
• 2.2 空间索引
• 2.2.1 空间索引分类
• 2.2.2 R 树索引
• 2.3 空间查询
• 2.3.1 空间选取
• 2.3.2 空间结合
• 2.4 最近邻问题
• 2.4.1 最近邻（NN）应用领域
• 2.4.2 kNN 搜索
• 2.5 本章小结
• 第3章 移动对象的动态反向最近邻
• 3.1 引言
• 3.2 基本定义
• 3.2.1 反向最近邻查询
• 3.2.2 TPR-树（Time Parameterized R-tree）
• 3.2.3 半平面修剪策略
• 3.3 移动对象的动态反向最近邻算法
• 3.3.1 基于矩形框对角线的判断方法
• 3.3.2 移动对象的动态反向最近邻算法
• 3.3.3 实例分析
• 3.4 本章小结
• 第4章 移动对象的动态反向K 最近邻
• 4.1 引言
• 4.2 移动对象的动态反向K 最近邻算法
• 4.2.1 反向k 最近邻
• 4.2.2 修剪策略
• 4.2.3 移动对象的动态反向k 最近邻算法
• 4.3 本章小结
• 第5章 算法的实验验证
• 5.1 引言
• 5.2 验证移动对象的动态反向 K 最近邻
• 5.2.1 实验设置
• 5.2.2 实验结果及结果分析
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢