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

发布时间：2018-01-13 23:26

本文关键词：面向位置服务的道路网络下的汽车索引技术研究　出处：《电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：近年来,随着卫星导航定位、无线通信等技术不断快速发展,由此带来了基于位置服务应用的大量涌现。当下社会交通网络的压力不断增大,面向道路网络的位置服务应用成为国家重点关注领域同时也被认为是未来国家之间技术竞争的战略制高点。移动对象数据库是相关位置服务系统中的数据管理中枢,而移动对象索引作为移动对象数据库中的关键性核心技术,其性能优劣直接影响着移动数据库效率的高低。是一个研究的热点问题。本文首先于第二章对各类索引进行研究分析,综述了各种索引的改进策略和性能的优劣。第三章中继而着重考虑了道路网络的特点,并以此建立了以路段为基础的道路路网模型。分析了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、设计并实现面向位置查询服务的原型系统。原型系统具有轨迹查询、范围查询、近邻查询、单点查询、轨迹预测等功能,可以通过模块化的形式导入索引模块来测试索引性能。
[Abstract]:In recent years, along with the development of satellite navigation and positioning, wireless communication technology has been rapid development, which brought about the emergence of a large number of location service application based on network traffic. The social pressure is increasing, location service application oriented road network has become the national focus areas are also regarded as strategic point of technology competition between countries in the future. Moving object database is the central position of the system, and the index of moving objects is the key core technology of mobile database, its performance directly affects the efficiency of the mobile database. It is a hot topic in the study. Firstly, in the second chapter of the various index of research and analysis, summarized and improvement strategies the performance index of the pros and cons. The third chapter focuses on the characteristics of the relay and the road network, and builds up the road to Model of road network based. The analysis of R-Tree and Quad-Tree as the index structure of the advantages and disadvantages. And put forward the main index structure based on the idea of double structure, analyzes the characteristics of Morton encoding and Hilbert encoding, the proposed auxiliary index structure MPT. Morton code and Patricia tree based on Morton codes was proposed based on the principle of mapping fast encoding algorithms for QMEA. fourth chapter explains the related algorithm index structure is proposed in the third chapter, the fifth chapter describes the design and implementation of a prototype system for location query service, the sixth chapter expounds the index structure and coding algorithm performance test, and the experimental results are analyzed. This paper is to put forward the index structure and encoding algorithm, this algorithm is related to the indexing structure based on the design and implementation of the prototype system, performance evaluation index and encoding algorithm and experimental result analysis As a clue to the text. The main work is as follows: 1, according to MON double index update performance and query efficiency, the double-layer structure proposed main index structure of CNR. upper and lower network add hash table hash table to improve the efficiency and update performance based on index. Through the integration of operation CNR and Morton code, the CNR has high response ability range query. In the sixth chapter, the experiment proves that CNR is the mainstream network index structure MON update operation efficiency is higher, and the response path query and range query better.2, based on Patricia tree and Morton code presents a one-dimensional index structure (Morton MPT Patricia Tree), through the improved structure of Patricia tree and correlation algorithm to improve the operating efficiency of index, the fusion index structure and Morton code, and proposes the nearest neighbor algorithm based on MPT, it makes the index structure Have the ability to query fast response. The two-dimensional spatial division, converts the block after the area for one-dimensional encoding, MPT index has efficient regional query ability. Analysis of sources of error range of Morton based on the query, and propose solutions. The sixth chapter of the Ming MPT Hash table, Trie tree the mainstream one dimensional index structure queries faster. MPT nearest neighbor search algorithm based on R-Tree nearest neighbor search algorithm with higher efficiency based on the.3 mapping principle proposed QMEA Morton code for fast encoding algorithm based on QMEA algorithm, the time complexity is a constant order. In the sixth chapter of experiments show that.QMEA has more practical application ability than Morton encoding algorithm the iterative principle based on the realization of the code, the encoding length range is generally used in the road network in the query, the QMEA algorithm is better encoding efficiency of.4, the design and implementation of the original query service oriented position The prototype system has the functions of track query, range query, nearest neighbor query, single point query and trajectory prediction. It can test index performance by modularized import index module.

【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495;TP311.13

【参考文献】