基于Hadoop分布式地图匹配算法的研究与实现

发布时间：2018-01-19 06:16

本文关键词： 地图匹配智能交通浮动车云平台　出处：《浙江工业大学》2015年硕士论文　论文类型：学位论文

【摘要】：随着现代智能交通系统(ITS)的快速发展,地理信息技术、卫星定位技术和观代通信技术在解决城市智能交通方面发挥了巨大的作用。浮动车数据作为智能交通系统的重要组成部分,是一种新型的城市出行规划方式和路况信息获取方式。地图匹配技术是浮动车数据处理中最关键的内容之一,只有判断出车辆在哪条道路上行驶,才能将GPS数据转化为有效的道路交通状态信息。云计算是一种将计算过程分摊到集群机器中,使得每台机器同时运算整个过程的不同部分,分担的任务最终合并结果,从而快速、有效的得到最终结果。本文主要工作阐述如下:(1)在地图匹配系统中,提出了一种新型的HashMap网格索引算法。该算法使时间复杂度降为O(1),解决了传统四叉树索引算法在空间对象分布不均匀时查询效率急剧下降的问题,且通过二次网格划分和一次中心区域划分,使得匹配准确度得到了较大地提升。(2)在地图匹配系统中引入海拔高程信息,将地图匹配算法拆分为高架/非高架匹配算法,待匹配点通过判断所在网格缓冲区内是否包含高架路段信息来选择匹配算法,改进了传统算法在处理高架和地面道路重叠时的不足,从而进一步提高了匹配准确度。(3)针对大规模浮动车数据在传统单机计算模型中进行地图匹配存在耗时大的问题,本文基于Hadoop云平台,通过Map/Reduce编程模型,对大规模浮动车数据进行分布式并行计算,实现了对地图匹配快速有效地处理。(4)通过对单车跟踪匹配测试、对高架和地面道路重叠时匹配测试、对大规模浮动车数据匹配测试,得出本文的算法在正确率和计算效率两方面均有较好的表现。
[Abstract]:With the rapid development of modern intelligent transportation system (ITS), geographic information technology (GIS). Satellite positioning technology and generation communication technology have played a great role in solving urban intelligent transportation. Floating vehicle data is an important part of intelligent transportation system. Map matching technology is one of the most important contents in floating vehicle data processing, only to determine which road the vehicle is driving on. Cloud computing is a kind of distributed computing process to cluster machines, so that each machine at the same time calculate different parts of the whole process. The shared tasks are combined to get the final results quickly and effectively. The main work of this paper is as follows: 1) in the map matching system. A new HashMap grid indexing algorithm is proposed, which reduces the time complexity to OF-1). It solves the problem that the query efficiency of the traditional quadtree index algorithm drops sharply when the spatial object distribution is not uniform, and through the quadratic grid division and the primary center region division. So that the matching accuracy is greatly improved. 2) the elevation information is introduced into the map matching system, and the map matching algorithm is divided into elevated / non-elevated matching algorithm. By judging whether the grid buffer contains elevated section information, the matching algorithm is selected, which improves the shortcomings of the traditional algorithm in dealing with the overlap of elevated and ground roads. Therefore, the matching accuracy is improved further.) aiming at the problem of large scale floating vehicle data matching in traditional single machine computing model, this paper is based on Hadoop cloud platform. Through the Map/Reduce programming model, the data of large-scale floating vehicle is computed in distributed parallel, and the map matching is processed quickly and effectively. The matching test of overlay and ground roads and the matching test of large-scale floating vehicle data show that the algorithm presented in this paper has good performance in both accuracy and computational efficiency.
【学位授予单位】：浙江工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495

【参考文献】