大规模轨迹数据并行化地图匹配算法

Parallelized Map Matching Algorithm for Large Scale Trajectory Data

为解决大规模轨迹数据的地图匹配问题,提出一种并行化的地图匹配算法。该算法将数据转换为弹性分布式数据集,利用Spark算子并行化计算出轨迹点的匹配路段,对原始GPS轨迹点进行校正,并采用GeoHash编码对候选路段的选取进行优化。采用Spark集群平台和约14.7 GB的西安市出租车轨迹数据对方案的规模增长性、加速比和可扩展性等性能进行了实验分析,并与一种基于Hadoop的同类地图匹配算法进行了性能比较,实验结果显示所设计算法效率提高了约31倍,表明本方案有较大的改进。

In order to solve the problem of the map matching for large scale trajectory data,a parallel map matching algorithm is proposed.The algorithm transforms the data into a resilient distributed dataset,the Spark operator is used to calculate the matching segments of the track points in parallel,the original GPS track points are corrected,and the selection of candidate segments are optimized by GeoHash coding.Using Spark cluster platform and Xi'an taxi track data about 14.7 GB,the performances of the scheme,such as scale growth,acceleration ratio and scalability,were analyzed experimentally,and compared with a similar map matching algorithm based on Hadoop.The experimental results show that the efficiency of the designed algorithm is improved by about 31 times,which indicate that the scheme has a great improvement.