基于路网的最近邻查询方法的研究.pdf

基于路网的最近邻查询方法的研究天津理工大学研究生学位论文昵胨妒垦学科专业:计算机软件与理论现代数据库技术作者姓名:肖迎元年研究方向:指导教师:王恒分类号:密级:
’
导师签名:缸易√学位论文作者签名:虏湃学位论文版权使用授权书独创性声明签字日期:少/少年签字日期:少/≥年夕月冶日卅签字日期:.加/二年力月墨盗墨墨太鲎墨盗墨兰盘鲎有关保留、使用学位论文的规定。特授权墨盗墨墨太堂学位论文作者签名:本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本学位论文作者完全了解可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编,以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子C艿难宦畚脑诮饷芎笫视帽臼谌ㄋ得文件。
摘要随着移动计算、全球定位系统以及地理信息等技术的迅速发展,特别是无线网络技术的同益盛行,基于位置的服务得到了广泛的应用。最近邻查询作为基于位置服务中最重要的查询类型,引起了众多学者的关注和深入研究。现有的最近邻查询,大多是基于欧式空间的查询。然而,现实生活中的大多数查询请求是基于网络空间的,并且现有基于欧式空间的查询处理方法不能直接应用于网络空间。因此,基于网络空间的查询得到了深入研究。但是,现存的基于网络空间的最近邻查询处理方法大多依赖网络空间中查询对象的密度,并随着查询对象数目脑龃螅询性能会迅速降低。针对这一问题,本文对基于路网的最近邻查询处理方法进行了研究,提出了基于预计算策略的查询处理方法。具体地,本文基于非交叉点子路径的预计算定理,提出了跳跃式查询最近邻的处理方法。该方法通过预计算获得交叉点的最近邻列表,利用网络扩展性,跳跃式查询相邻交叉点的最近邻列表。从而弥补了现有处理技术的不足,有效的降低了预计算的代价。进一步,本文提出了分治查询连续最近邻的处理方法,该方法利用非交叉点子路径的特点,通过分治法确定查询路径的划分点。该方法不但降低了预计算的代价,并且从很大程度上提高了查询的性能。特别是交叉点密度稀疏的查询路径上,查询性能更加优最后,通过设计大量的仿真试验,在页访问次数和执行时间两方面,验证了本文处理方法的氯沸院陀行浴关键词:基于位置服务最近邻查询预计算策略跳跃式查询分治法越。
.,·,甅瑃瑆—篖狟,琱,瑆瑆猧,..
第一章引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..第二章相关概念与基础理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯第三章跳跃式查询最近邻处理方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..目录研究背景及意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...芯勘尘啊璲⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.芯恳庖濉国内外研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。.⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯研究内容⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.本文组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯网络空间基础⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...ぜ扑慊±⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..典型的查询处理方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯矸椒ā处理方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.跳跃式最近邻查询算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。.⒔ .
第四章基于分治查询连续最近邻查询处理方法⋯.⋯⋯⋯⋯⋯⋯⋯⋯⋯第五章实验设计与评估⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯第六章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.发表论文和科研情况说明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..典型的查询处理方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.矸椒ā矸椒ā基于分治的连续最近邻查询算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯基本思想⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⒔峁股杓啤.