Parallel Distributed Trajectory Pattern Mining Using Hierarchical Grid with MapReduce
Parallel Distributed Trajectory Pattern Mining Using Hierarchical Grid with MapReduce
复制标题
DOI：
10.4018/ijghpc.2013100106
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Kazuhiro Seki;Ryota Jinno;K. Uehara
中科院分区：
文献类型：
--
作者：
Kazuhiro Seki;Ryota Jinno;K. Uehara
本文提出了一种新的轨迹模式挖掘方法，试图从运动对象的轨迹中发现频繁的运动模式。传统的弹道数据处理方法在处理大量弹道数据时，采用固定分辨率的网格划分。然而，适当的分辨率通常在轨迹的不同区域之间变化。简单地提高分辨率无法捕获广泛的模式，并且会消耗不必要的大量计算资源。为了解决这个问题，作者提出了一个层次化的基于网格的方法与四叉树搜索。该方法最初使用粗网格搜索频繁模式，然后深入到更细的网格级别以发现更多微小的模式。该算法是自然并行化的，并在MapReduce编程模型中实现，以加速计算。作者在真实数据上的评估实验表明，作者的方法在挖掘复杂模式时具有较低的计算成本。
This paper proposes a new approach to trajectory pattern mining, which attempts to discover frequent movement patterns from the trajectories of moving objects. For dealing with a large volume of trajectory data, traditional approaches quantize them by a grid with a fixed resolution. However, an appropriate resolution often varies across different areas of trajectories. Simply increasing the resolution cannot capture broad patterns and consumes unnecessarily large computational resources. To solve the problem, the authors propose a hierarchical grid-based approach with quadtree search. The approach initially searches for frequent patterns with a coarse grid and drills down into a finer grid level to discover more minute patterns. The algorithm is naturally parallelized and implemented in the MapReduce programming model to accelerate the computation. The authors' evaluative experiments on real-word data show the effectiveness of the authors' approach in mining complex patterns with lower computational cost than the previous work.