基于区域覆盖的移动对象K近邻查询算法的研究与实现

论文摘要

近年来,随着科技的发展,与位置服务有关的定位技术、导航技术、监控技术已经广泛走进现实生活。如今,手机、车载设备等电子产品提供位置服务相关功能越来越普遍。这些应用的技术基础空间数据库的研究也越来越成为热点问题之一。其中移动对象的K近邻查询就是空间数据库中重要的应用之一。例如,在交通管理中,一辆出租车要查找当前时刻距它最近的前K个旅馆或加油站,使出租车司机可以选择一个离自己不远又顺路的结果；在战争中,一个战士要查找自己附近的人员的位置情况；在航海中,一艘轮船要查询距离自己较近的若干艘轮船等。尽管K近邻查询的研究工作已有很多成果,但对在大量移动对象频繁移动的环境下,现有索引在高效更新,快速近邻查询方面表现不是很理想。因此,本文从该问题作为切入点,进行了深入研究。首先,本文通过分析移动对象在频繁移动情况下进行k近邻查询的难点——查询与更新的特性,利用网格文件解决频繁更新的问题,利用Voronoi图解决近邻查询的问题,提出了一种基于区域覆盖的虚拟网格四分树（Virtual Grid Quadtree, VGQ）与Voronoi Diagram相结合（Vor-VGQ）的索引结构。结合两种结构的优点,该索引适合近邻查询并且支持动态更新。它通过索引移动对象所在区域而非移动对象本身来减少由于移动对象位置改变而引起的索引结构的更新。其次,在Vor-VGQ索引结构基础上做了2种策略的K近邻处理方法。一种面向于提高查询效率的实时动态Voronoi Diagram变换策略,随着网格的变化Voronoi Diagram同步变化。在试验过程中发现路网中数据分布的相对稳定性,从而提出了面向于提高更新效率的单调动态Voronoi Diagram更新策略,最终形成依据路网分布的稳定的Voronoi Diagram结构。利用上述两种策略设计了范围查询和KNN查询的算法,并且证明了算法的准确性。最后,本文设计了实验并进行了对比分析。实验结果表明,Vor-VGQ是一种高效的空间数据索引结构,基于Vor-VGQ索引结构的KNN查询与已有B+树类算法如BX树索引查询相比效率提高三个数量级。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 移动对象数据库
• 1.3 研究目的及意义
• 1.4 本文主要工作
• 1.5 本文组织结构
• 第2章 相关工作
• 2.1 移动对象索引技术
• 2.1.1 研究现状
• 2.1.2 索引的分类
• 2.2 K近邻查询的研究现状
• 2.3 本章小结
• 第3章 动态VORONOI图
• 3.1 移动数据模型
• 3.2 虚拟网格四分树
• 3.2.1 压缩四分树索引
• 3.2.2 四分树相关数据结构
• 3.3 动态Voronoi图
• 3.3.1 插入对象
• 3.3.2 删除对象
• 3.3.3 移动对象
• 3.3.4 性能分析
• 3.4 本章小结
• 第4章 VOR-VGQ索引结构及查询算法
• 4.1 问题提出
• 4.2 结构设计
• 4.3 索引结构的更新
• 4.3.1 插入操作
• 4.3.2 删除操作
• 4.3.3 移动操作
• 4.4 KNN查询
• 4.5 扩展——单调动态Vor-VGQ
• 4.6 本章小结
• 第5章 实验及结果分析
• 5.1 实验环境及实验设计
• 5.1.1 实验环境
• 5.1.2 实验数据集
• 5.2 实验数据及结果分析
• 5.3 结果分析
• 5.3.1 动态Vor-VGQ实验结果
• 5.3.2 单调动态Vor-VGQ实验结果分析
• 5.4 本章小结
• 第6章 总结与展望
• 6.1 内容总结
• 6.2 未来展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文和参加的项目