Parallel Distributed Trajectory Pattern Mining Using Hierarchical Grid with MapReduce

Parallel Distributed Trajectory Pattern Mining Using Hierarchical Grid with MapReduce

Kazuhiro Seki (Kobe University, Kobe, Japan), Ryota Jinno (Kobe University, Kobe, Japan) and Kuniaki Uehara (Kobe University, Kobe, Japan)
Copyright: © 2013 |Pages: 18
DOI: 10.4018/ijghpc.2013100106
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

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.
Article Preview

Introduction

With the advance of sensing technologies and the prevalence of GPS devices, trajectory data have been drawing much attention from the data mining community (Ahas et al., 2007; Benkert et al., 2008; Palma et al., 2008; Verhein & Chawla, 2006). Trajectory data can be of any moving objects, such as people, wild animals, automobiles, and even hurricanes. For any type of objects, analyzing their trajectories may reveal interesting patterns useful for various applications (Long & Nelson, 2013). For example, identifying the patterns of hurricane movement is beneficial to predict the course of hurricanes and analyzing the movement patterns of wild animals helps understanding their ecology (Lee et al., 2007). Also, analyzing movement patterns of people in a factory or an operating room is useful in designing an effective production line or safe arrangement of surgical instruments (Nara et al., 2010). However, trajectory data are typically large and identifying interesting patterns requires intensive analysis that cannot be manually done, where data mining techniques play an important role.

The research area in data mining which attempts to identify interesting patterns in trajectory data is called trajectory pattern mining (Giannotti et al., 2007). Generally, a trajectory of an object is represented as a series of location data and each location is associated with a particular time when the object is at the location (Hornsby & Egenhofer, 2002). Location data are typically recorded as geographic coordinates (latitude and longitude). Because such location data take up much memory space and is expensive to handle, grid-based approaches are often utilized.

Grid-based approaches quantize location data by cells defined by a mesh grid and could substantially reduce the memory requirement depending on the resolution of the grid. A drawback in adopting grid-based approaches is that the location information is no longer accurate. Increasing the resolution alleviates the problem but using too high resolution consumes unnecessarily large memory. Although a proper resolution could be determined considering the trade-off between accurateness and memory requirement, a fixed resolution is not suitable in the first place for identifying trajectory patterns. That is, dense regions should be represented with high resolution, and for sparse regions, the same level of granularity is inefficient and rather harmful as it will fail to see broad patterns.

Given the background, this paper proposes an approach to trajectory pattern mining using a hierarchical grid with quadtree search in order to identify complex patterns involving different levels of granularity. Specifically, we consider hierarchically structured multiple grids to represent trajectory data, where a deeper grid has higher resolution. Then, we search for frequent trajectory patterns starting from a coarse level and recursively drill down to a finer level to identify more minute patterns. The mining procedure is carried out for each cell and is naturally parallelized. We develop a trajectory pattern mining algorithm tailored to the MapReduce programming model for speedup and efficiency.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing