道路空间中连续最近邻居查询方法的研究

论文摘要

道路空间中连续最近邻居问题(CKNN)是近年来研究领域中的热点问题,并且被广泛地应用在地理信息系统中。CKNN的初衷是找到待查询路径上任意查询点的最近邻居集,其结果是待查询路径上的一系列分割点,这些分割点将原待查询路径分成若干段,使得落在同一段上的查询点具有相同的最近邻居集。连续最近邻居问题的一个重要研究意义在于可以采用预处理技术,将道路空间中路径的最近邻居信息事先存储。在用户要求查询道路空间中某一点的最近邻居集时,系统可以快速返回查询结果。在道路空间中,两个目标点之间的距离是用连接它们的最短路径的长度来衡量。目前,道路空间中连续最近邻居问题的查询方法主要分为两大类:一类是基于分治思想的,例如IE方法;另一类是基于距离函数的,其代表是UNICONS方法。本文提出了一种道路空间中连续最近邻居的查询方法——Split方法。Split方法采用分而治之的思想,将待查询路径分割成若干子路径,通过每一条子路径端点的最近邻居集求得各子路径的连续最近邻居,最后合并各条子路径上的结果,从而得到待查询路径的连续最近邻居查询结果。本文完成了Split方法和其它道路空间中连续最近邻居查询方法——IE和UNICONS的对比实验。实验证明,在实际应用中,Split方法效率高于IE方法,在稠密目标点数据集中,Split方法的性能优于UNICONS方法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究意义与现状
• 1.2 本文主要工作及结构
• 第二章 背景知识及相关工作
• 2.1 道路空间中的CKNN问题
• 2.2 IE
• 2.3 UNICONS
• 2.3.1 距离可以用线性方程表示
• 2.3.2 记录距离的坐标方式
• 2.3.3 UNICONS的计算过程
• 2.3.4 UNICONS方法的优化
• 第三章 一种基于分治的连续最近邻居查询方法——Split
• 3.1 道路空间中的重要概念
• 3.2 道路空间中KNN和CKNN的关系
• 3.3 分而治之的思想和Split方法框架
• 3.3.1 分而治之的思想
• 3.3.2 Split方法解决CKNN的框架
• 3.4 待查询路径的分解
• 3.5 求解子路径端点KNN的算法
• 3.6 计算子路径上的CKNN
• 3.6.1 理论基础
• 3.6.2 算法描述
• 3.6.3 算法分析
• 第四章 实验
• 4.1 实验环境与实验数据
• 4.1.1 实验环境
• 4.1.2 实验数据
• 4.2 实验结果及分析
• 4.2.1 UNICONS的计算过程
• 4.2.2 IE方法和Split方法在子路径上的性能比较
• 4.2.3 UNICONS方法和Split方法在不同密度目标点道路空间中的性能比较
• 第五章 总结与展望
• 第六章 参考文献
• 第七章 致谢