A MapReduce-Based Parallel Frequent Pattern Growth Algorithm for Spatiotemporal Association Analysis of Mobile Trajectory Big Data
A MapReduce-Based Parallel Frequent Pattern Growth Algorithm for Spatiotemporal Association Analysis of Mobile Trajectory Big Data
复制标题
基于MapReduce的移动轨迹大数据时空关联分析并行频繁模式增长算法
DOI：
10.1155/2018/2818251
复制
发表时间：
2018
期刊：
影响因子：
2.3
通讯作者：
Zhang Zili
中科院分区：
文献类型：
--
作者：
Xia Dawen;Lu Xiaonan;Li Huaqing;Wang Wendong;Li Yantao;Zhang Zili
频繁模式挖掘是数据驱动的智能交通系统中移动轨迹大数据时空关联分析的有效方法。虽然现有的并行算法已成功应用于大规模轨迹数据的频繁模式挖掘，但两大挑战是如何克服Hadoop的固有缺陷来应对包括海量小文件的出租车轨迹大数据以及如何利用MapReduce发现隐式时空频繁模式。为了克服这些挑战，本文提出了一种基于MapReduce的并行频繁模式增长（MR-PFP）算法，在Hadoop平台上使用大规模出租车轨迹和海量小文件处理策略来分析出租车运营的时空特征。更具体地说，我们首先实现三种方法，即Hadoop Archives (HAR)、CombineFileInputFormat (CFIF)和Sequence Files (SF)，以克服Hadoop现有的缺陷，然后根据它们的性能评估提出两种策略。接下来，我们将SF纳入频繁模式增长（FP-growth）算法中，然后在MapReduce框架上实现优化的FP-growth算法。最后，我们通过MR-PFP并行分析了出租车在空间和时间维度上的运营特征。结果表明，MR-PFP 在效率和可扩展性方面优于现有的并行 FP 增长（PFP）算法。
Frequent pattern mining is an effective approach for spatiotemporal association analysis of mobile trajectory big data in data-driven intelligent transportation systems. While existing parallel algorithms have been successfully applied to frequent pattern mining of large-scale trajectory data, two major challenges are how to overcome the inherent defects of Hadoop to cope with taxi trajectory big data including massive small files and how to discover the implicitly spatiotemporal frequent patterns with MapReduce. To conquer these challenges, this paper presents a MapReduce-based Parallel Frequent Pattern growth (MR-PFP) algorithm to analyze the spatiotemporal characteristics of taxi operating using large-scale taxi trajectories with massive small file processing strategies on a Hadoop platform. More specifically, we first implement three methods, that is, Hadoop Archives (HAR), CombineFileInputFormat (CFIF), and Sequence Files (SF), to overcome the existing defects of Hadoop and then propose two strategies based on their performance evaluations. Next, we incorporate SF into Frequent Pattern growth (FP-growth) algorithm and then implement the optimized FP-growth algorithm on a MapReduce framework. Finally, we analyze the characteristics of taxi operating in both spatial and temporal dimensions by MR-PFP in parallel. The results demonstrate that MR-PFP is superior to existing Parallel FP-growth (PFP) algorithm in efficiency and scalability.