大数据平台下地图匹配算法的研究与实现
发布时间：2018-11-05 07:45
【摘要】：本文为了进一步满足处理海量GPS数据的精度与速率的要求,主要完成了地图匹配算法在精度上的改进和改进后地图匹配算法在MapReduce并行计算框架上的并行化设计与实现。针对海量GPS数据分析的精度问题,主要是分析一些现有地图匹配算法在现实生活中运用场景的优缺点,结合部分地图匹配算法的优点与本人的一些研究成果,提出一种结合部分交通规则的地图匹配算法。该算法主要借用隐马尔可夫模型(Hidden Markov Model,HMM)对地图匹配过程进行建模,充分考虑了前后GPS信息和电子地图中的路网拓扑关系,提高了地图匹配算法的精度,以进一步满足海量GPS数据的挖掘需求。本文完成了包括噪声数据过滤、冗余数据去除、缺失数据补充和漂移数据修正的GPS数据预处理过程,改进的地图匹配算法的设计与实现以及与之对比的一种拓扑信息的地图匹配算法的设计与实现等工作,通过与基于拓扑信息的地图匹配算法在精度和处理速度上进行对比,得出在处理文章中所给的采样频率的GPS数据上,改进后的地图匹配算法匹配结果的精度更高。针对海量GPS数据处理速度的问题,本文主要对地图匹配算法的并行化进行了研究。该问题的研究意义在于更快的处理大量时空数据的地图匹配问题,提高处理的速率,节约时间成本。本文完成了包括噪声数据去除并行化、冗余数据去除并行化、缺失数据补充并行化和漂移数据修正并行化的GPS数据预处理过程的并行化,改进的地图匹配算法并行化的设计与实现以及与之对比的改进的地图匹配算法单机版本的设计与实现等工作,通过对比地图匹配算法的单机版本和并行化版本的结果和执行时间,得出了基于MapReduce计算框架设计的地图匹配算法设计的正确性,同时也得出了该并行版本所耗时间最短,而且在数据量逐渐增大时,这种实现方法相比其他两种在速率上的优势更大,进而得出这种并行化算法在处理大量数据的优越性。
[Abstract]:In order to meet the requirements of accuracy and speed of processing massive GPS data, this paper mainly completes the design and implementation of the improved map matching algorithm in the framework of MapReduce parallel computing. Aiming at the accuracy of massive GPS data analysis, this paper mainly analyzes the advantages and disadvantages of some existing map matching algorithms in real life, and combines the advantages of some map matching algorithms with some of my research results. A map matching algorithm combining partial traffic rules is proposed. The algorithm mainly uses hidden Markov model (Hidden Markov Model,HMM) to model the map matching process, fully considers the GPS information and the network topology relationship in the electronic map, and improves the accuracy of the map matching algorithm. In order to further meet the massive GPS data mining needs. In this paper, the GPS data preprocessing process including noise data filtering, redundant data removal, missing data supplement and drift data correction is completed. The design and implementation of the improved map matching algorithm and the design and implementation of a map matching algorithm based on topological information are compared with the map matching algorithm based on topology information in precision and processing speed. It is concluded that the improved map matching algorithm is more accurate in processing the GPS data of sampling frequency given in the paper. Aiming at the problem of processing speed of massive GPS data, this paper mainly studies the parallelization of map matching algorithm. The research significance of this problem is to deal with the map matching problem of a large amount of space-time data more quickly, to improve the processing rate and to save time cost. This paper completes the parallelization of GPS data preprocessing, which includes noise data removal parallelization, redundant data removal parallelization, missing data supplement parallelization and drift data correction parallelization. The design and implementation of the parallelization of the improved map matching algorithm and the design and implementation of the single version of the improved map matching algorithm are also presented. By comparing the results and execution times of the single and parallel versions of the map matching algorithm, the correctness of the map matching algorithm design based on the MapReduce computing framework is obtained, and the shortest time consumed by the parallel version is also obtained. Moreover, when the amount of data increases gradually, this method has more advantages than the other two methods in the speed, and then obtains the superiority of this parallel algorithm in dealing with a large number of data.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：P228.4;TP311.13
[Abstract]:In order to meet the requirements of accuracy and speed of processing massive GPS data, this paper mainly completes the design and implementation of the improved map matching algorithm in the framework of MapReduce parallel computing. Aiming at the accuracy of massive GPS data analysis, this paper mainly analyzes the advantages and disadvantages of some existing map matching algorithms in real life, and combines the advantages of some map matching algorithms with some of my research results. A map matching algorithm combining partial traffic rules is proposed. The algorithm mainly uses hidden Markov model (Hidden Markov Model,HMM) to model the map matching process, fully considers the GPS information and the network topology relationship in the electronic map, and improves the accuracy of the map matching algorithm. In order to further meet the massive GPS data mining needs. In this paper, the GPS data preprocessing process including noise data filtering, redundant data removal, missing data supplement and drift data correction is completed. The design and implementation of the improved map matching algorithm and the design and implementation of a map matching algorithm based on topological information are compared with the map matching algorithm based on topology information in precision and processing speed. It is concluded that the improved map matching algorithm is more accurate in processing the GPS data of sampling frequency given in the paper. Aiming at the problem of processing speed of massive GPS data, this paper mainly studies the parallelization of map matching algorithm. The research significance of this problem is to deal with the map matching problem of a large amount of space-time data more quickly, to improve the processing rate and to save time cost. This paper completes the parallelization of GPS data preprocessing, which includes noise data removal parallelization, redundant data removal parallelization, missing data supplement parallelization and drift data correction parallelization. The design and implementation of the parallelization of the improved map matching algorithm and the design and implementation of the single version of the improved map matching algorithm are also presented. By comparing the results and execution times of the single and parallel versions of the map matching algorithm, the correctness of the map matching algorithm design based on the MapReduce computing framework is obtained, and the shortest time consumed by the parallel version is also obtained. Moreover, when the amount of data increases gradually, this method has more advantages than the other two methods in the speed, and then obtains the superiority of this parallel algorithm in dealing with a large number of data.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：P228.4;TP311.13
【参考文献】
相关期刊论文 前6条
1 王美玲;程林;;浮动车地图匹配算法研究[J];测绘学报;2012年01期
2 杨U，
本文编号：2311379
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/2311379.html
