详情

原文传递面向位置服务的道路网络下的汽车索引技术研究

论文题名：	面向位置服务的道路网络下的汽车索引技术研究
关键词：	道路网络;汽车索引;位置服务;更新操作
摘要：	近年来，随着卫星导航定位、无线通信等技术不断快速发展，由此带来了基于位置服务应用的大量涌现。当下社会交通网络的压力不断增大，面向道路网络的位置服务应用成为国家重点关注领域同时也被认为是未来国家之间技术竞争的战略制高点。移动对象数据库是相关位置服务系统中的数据管理中枢，而移动对象索引作为移动对象数据库中的关键性核心技术，其性能优劣直接影响着移动数据库效率的高低。是一个研究的热点问题。　　本文首先于第二章对各类索引进行研究分析，综述了各种索引的改进策略和性能的优劣。第三章中继而着重考虑了道路网络的特点，并以此建立了以路段为基础的道路路网模型。分析了R-Tree和Quad-Tree作为索引结构的优劣势。并提出基于双层结构思想的主索引结构，分析了Morton编码和Hilbert编码的特点，提出基于 Morton码和 Patricia树的辅助索引结构 MPT。基于映射原理提出 Morton码快速编码算法 QMEA。第四章中阐述了第三章中提出的索引结构的相关算法，第五章中阐述了面向位置查询服务的原型系统的设计与实现，第六章中阐述了针对索引结构和编码算法性能测试的实验，并对实验结果进行分析。论文大致以：索引结构及编码算法的提出、基于提出的索引结构的相关算法阐述、原型系统设计与实现、索引及编码算法性能评估及实验结果分析为线索来组织全文。　　文本的主要工作为以下几点：　　1、针对MON等双层索引的更新性能和查询效率不高的缺点，基于双层结构思想提出主索引结构 CNR。添加上层路网哈希表和下层哈希链表以提高了索引的操作效率和更新性能。通过融合CNR和Morton码，使得CNR具有高效响应范围查询的能力。第六章中的实验证明CNR较主流路网索引结构MON的更新操作效率更高，且响应轨迹查询和范围查询的能力更佳。　　2、基于Patricia树和Morton码提出一种一维索引结构MPT（Morton Patricia Tree），通过改良Patricia树的结构和相关算法以提高索引的操作效率，融合索引结构和Morton码，并提出基于MPT的近邻算法，使得索引结构具有快速响应近邻查询的能力。将二维空间进行划分，把分块后的区域转换为一维编码，使MPT索引具有高效的区域查询能力。分析基于Morton的范围查询的误差来源，并提出解决方案。第六章中的实验证明MPT比Hash表，Trie树等主流一维索引结构的查询速度更快。基于MPT的近邻搜索算法比基于R-Tree的近邻搜索算法效率更高。　　3、基于映射原理提出Morton码快速编码算法QMEA，QMEA的算法时间复杂为常数阶。第六章中的实验证明。QMEA比基于迭代原理实现的Morton码编码算法更具实际应用能力，即在道路网络查询中一般使用的编码长度范围内，QMEA算法的编码效率较优。　　4、设计并实现面向位置查询服务的原型系统。原型系统具有轨迹查询、范围查询、近邻查询、单点查询、轨迹预测等功能，可以通过模块化的形式导入索引模块来测试索引性能。
作者：	易显天
专业：	电子与通信工程
导师：	田忠
授予学位：	硕士
授予学位单位：	电子科技大学
学位年度：	2015
正文语种：	中文