基于Voronoi图的路网轨迹数据查询技术的分析.pdf

硕士学位论文题目:基于Voronoi图的路网轨迹数据查询技术研究研究生陈宇专业计算机应用技术指导教师徐建教授完成日期2015年3月杭州电子科技大学硕士学位论文万方数据基于Voronoi图的路网轨迹数据查询技术研究研究生:陈宇指导教师:徐建教授2015年3月万方数据Dissertation Submitted to Hangzhou Dianzi Universityfor the Degree of MasterThe Research on Technologies of Voronoi based Trajectory worksCandidate: ChenYuSupervisor: Prof. XuJianMarch, 2015万方数据杭州电子科技大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。申请学位论文与资料若有不实之处,本人承担一切相关责任。论文作者签名:日期:年月日学位论文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后,发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。(保密论文在解密后遵守此规定)论文作者签名:日期:年月日指导教师签名:日期:年月日万方数据杭州电子科技大学硕士学位论文I摘要移动互联和移动计算已逐步走进千家万户,带有定位功能的移动智能终端帮助人们实时记录移动历史,海量的轨迹数据信息反映了人们的行为信息和社交关系。多位置轨迹查询作为一种应用广泛的轨迹查询技术,已经成为当前的一个研究热点。多位置轨迹查询是搜索那些能连接多个查询位置点的轨迹,其查询结果依赖轨迹对多个位置的连接性。目前,多位置轨迹查询研究主要集中在欧式空间,没有考虑路网环境约束,且存在受轨迹数据集影响较大、查询效率不高和扩展性不好的问题。针对这些不足,本文对路网中的多位置轨迹查询技术进行了研究。首先,为了解决轨迹数据冗余性和异构性对轨迹查询的影响,本文提出了一种基于Voronoi图的路网轨迹数据简化算法。在考虑到采样轨迹数据中存在的冗余性和不同轨迹数据采样率不同的问题,对现有的轨迹简化处理技术进行了分析和总结,通过利用Voronoi图的空间近邻关系预计算特征和路网结构相对稳定特性来简化处理海量轨迹数据,使其统一为路网节点密度的路网语义轨迹。其次,针对路网约束下的多位置轨迹查询,论文提出了一种路网中基于Voronoi图的连接轨迹查询算法。该算法首先利用Voronoi图的近邻关系把每个查询位置转换成相应的路网节点,然后在给定的距离阈值范围内对查询节点进行网络范围查询,并通过合并所有查询节点的查询结果得到连接多个查询位置的轨迹,这不但保证了轨迹在每个查询位置的有限可达性,而且保证了多位置的连接性。最后,提出了一种基于路径距离的最佳连接轨迹查询算法。算法引入了轨迹路径距离的概念,能够满足最佳连接轨迹查询的应用需求。该算法不但要求轨迹近邻多个查询位置,而且需要根据轨迹对多位置连接的路网路径距离来衡量轨迹的连接性,并排名、输出最佳连接轨迹。这保证了最佳连接轨迹在距离阈值内近邻连接多查询位置的同时获得最短的连接路径距离。本文针对以上三个创新点展开了理论研究。在真实路网的模拟轨迹数据集上展开了实验研究,结果表明,本文介绍的方法可以有效的简化处理轨迹数据,尤其是高采样的轨迹数据。基于Voronoi图的多位置连接轨迹查询算法表现出比对比算法更好的查询性能和可扩展性。基于路径距离的最佳连接轨迹查询也表现出很好的查询性能。研究结果具有较好的应用前景。关键词:轨迹查询,轨迹简化,Voronoi图,位置,路网万方数据杭州电子科技大学硕士学位论文IIABSTRACTMobile and mobile computing has gradually stepped into thousands of families, the proliferation of GPS-enable smart devices enable people to log their geographical positions and to trace historical movement, the massive trajectory data reflect