道路网中基于方向关系约束的范围查询算法研究

《道路网中基于方向关系约束的范围查询算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER’SDISSERTATION论文题目道路网中基于方向关系约束的范围查询算法研究作者姓名刘向彦学科专业计算机应用技术指导教师刘永山教授2015年05月中图分类号：TP391.3学校代码：10216UDC：004密级：公开工学硕士学位论文道路网中基于方向关系约束的范围查询算法研究硕士研究生：刘向彦导师：刘永山教授申请学位：工学硕士学科专业：计算机应用技术所在单位：信息科学与工程学院答辩日期：2015年05月授予学位单位：燕山大学-II-ADissertationinComputerApplicationTechnologyRE

2、SEARCHONRANGEQUERYBASEDONCONSTRAINTOFDIRECTIONALRELATIONALGORITHMINROADNETWORKbyLiuXiangyanSupervisor:ProfessorLiuYongshanYanshanUniversityMay，2015燕山大学工学硕士学位论文燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《道路网中基于方向关系约束的范围查询算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写

3、过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学硕士学位论文使用授权书《道路网中基于方向关系约束的范围查询算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全

4、部或部分内容。保密□，在年解密后适用本授权书。本学位论文属于不保密□。(请在以上相应方框内打“√”)作者签名：日期：年月日导师签名：日期：年月日-IV-摘要随着无线通信，GPS空间定位，位置服务等技术的飞速发展，以及众多具有定位功能的无线手持和车载设备的大量普及，尤其国内新近兴起的打车软件的广泛应用，位置服务早已成为一个前景广阔的朝阳产业，得到了越来越多的关注。其中一个典型的需求就是对道路网中移动对象进行连续测控，比如连续查询“距离目前位置5km之内的所有出租车”等实际问题。现有的移动对象范围查询方法大多都假设移动对象在欧式空间中自由运动。这些方

5、法只能服务于特定领域，然而在现实生活中大多数用户和移动对象是受限于道路网络的，因此用户和移动对象之间的距离用网络距离来衡量更加合理。新近开始研究的基于网络距离的道路网增量式范围查询算法又存在盲目扩张的缺点。基于上述分析本文的研究工作如下：首先本文在现有的移动对象数据库索引和查询处理技术等方面的最新成果基础上，研究重点集中于包括双行道和单行道组成的道路网中的移动对象连续范围查询处理问题上。提出了基于方向关系约束增量式范围查询(IncrementalrangequeryBasedonConstraintofDirectionalRelation，CD

6、R-IRQ)算法。该算法过滤掉一部分与查询点运动方向相反的无效道路边加快了范围查询的速度。其次对于数据分布集中的道路网，同一路径上很多查询点的查询结果集都有相关性有些甚至完全相同，针对这一特点在CDR-IRQ算法的基础上提出了基于方向关系约束的组范围查询(GrouprangequeryBasedonConstraintofDirectionalRelation，CDR-GRQ)算法。该算法以路径为单位，同一路径上的所有查询点共享范围查询执行过程，以此减少算法的重复计算，进一步提高查询的效率。最后本文进行了实验对比和分析，实验结果表明CDR-IRQ

7、算法在道路边上移动对象分布比较均匀时查询效率较优，而CDR-GRQ算法在道路边上移动对象分布比较集中时查询效率较优，而且这两种算法均优于在增量式范围查询时盲目扩张的原始算法。关键词：道路网；范围查询；增量式范围查询；方向关系约束；组范围查询燕山大学工学硕士学位论文AbstractWiththerapiddevelopmentofwirelesscommunication,GPSlocation,computertechnologyandothertechnologies,aswellasthegreatpopularizationofnumero

8、usofwirelesshand-heldandin-cardeviceswhichhavepositioningfunction,es