Moving Objects Gathering Patterns Retrieving based on Spatio-Temporal Graph

Moving Objects Gathering Patterns Retrieving based on Spatio-Temporal Graph

Junming Zhang (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, China), Jinglin Li (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, China), Zhihan Liu (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, China), Quan Yuan (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, China) and Fangchun Yang (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, China)
Copyright: © 2016 |Pages: 20
DOI: 10.4018/IJWSR.2016070105
OnDemand PDF Download:
$37.50

Abstract

Moving objects gathering pattern represents a group events or incidents that involve congregation of moving objects, enabling the analysis of traffic system. However, effectively and efficiently discovering the specific gathering pattern turns to be a remaining challenging issue since the large number of moving objects will generate high volume of trajectory data. In order to address this issue, the authors propose a moving object gathering pattern retrieving method that aims to support the retrieving of gathering patterns based on spatio-temporal graph. In this method, firstly the authors use an improved R-tree based density clustering algorithm (RT-DBScan) to index the moving objects and collect clusters. Then, they maintain a spatio-temporal graph rather than storing the spatial coordinates to obtain the spatio-temporal changes in real time. Finally, a gathering retrieving algorithm is developed by searching the maximal complete graphs which meet the spatio-temporal constraints. To the best of their knowledge, effectiveness and efficiency of the proposed methods are outperformed other methods on both real and large trajectory data.
Article Preview

1. Introduction

The increasing availability of location acquisition has been applied to GPS on vehicles. The technology has enabled tracking almost any moving behaviors of moving objects, which results in huge volumes of spatio-temporal data in the form of trajectories. Movement pattern can be observed from this kind of data. The movement pattern will provide useful information for traffic jam prediction and traffic flow control.

In order to support the traffic analysis application, we have to investigate the group spatial-temporal movement pattern. In contrast to spatial movement patterns, spatio-temporal movement patterns take the time information in a trajectory into account. Having a time constraint, the movement pattern is therefore stricter than a spatial movement pattern. The time constraint can help discover more specific patterns in many cases of mining trajectory data. For example, detecting the traffic overload regions by analyzing the large groups of vehicles should take into account the time information of the trajectory data. Therefore, attentions have been paid to analyze movement pattern for traffic analysis by using such data (Kuijpers & Othman, 2009; Pfoser & Jensen, 2003). Some researchers are trying to use trajectory data providing navigation services and route planning services.

One of the most useful movement pattern analysis tasks in trajectory data mining is to find moving object gatherings (the gathering, for short), which is first defined in (Zheng, Zheng, Yuan, & Shang, 2013). Informally, a gathering represents a group event or incident that involves congregation of moving objects (e.g. vehicles). In order to monitor and predicate the traffic anomalies, Zheng (Zheng et al., 2013) proposes a gathering pattern discovery method by counting the gathering number. Specifically, it use the spatial Gird to index the crowd of moving objects, and then use the Crowd-TAD method to test each crowd to discover the gathering pattern.

However, the huge volume of trajectory data makes it difficult to estimate meaningful gathering movement pattern with certain spatio-temporal constraints. To address this issue, a crowd discovery method can be used to find a group of moving objects from a long history of recorded trajectories. A crowd is a sequence of spatial clusters that appear in consecutive snapshots of the object movements and form a gathering if they move to one direction. Previous works has shown that this method could be used to discover crowd from trajectory (Kalnis, Mamoulis, & Bakiras, 2005; Li, Ding, Han, & Kays, 2010), and gathering discovery algorithm is further illustrated in (Zheng et al., 2013). However, these algorithms could only get a gathering set from the trajectory and the algorithm proposed in ref (Zheng et al., 2013) cannot retrieve the gathering in one place or in a time period. If gathering cannot be retrieved from trajectory data, it can be said, the discovery of such patterns will be meaningless. The previous work of moving pattern retrieving concerns on the aspects of group mining (De Almeida & Güting, 2005; Demiryurek, Pan, Banaei-Kashani, & Shahabi, 2009; Güting, de Almeida, & Ding, 2006; SimonasˇSaltenis, Leutenegger, & Lopez, 1999; Šaltenis, 2000, p. 25}. In this case, we can use the spatio-temporal graph to model the variations of moving clusters, and a gathering retrieving algorithm will be designed to retrieve gatherings from the graph effectively and efficiently.

In order to retrieve gathering pattern from huge trajectories effectively and efficiently, we propose a gathering retrieving method based on spatio-temporal graph that forms by moving object clusters. The main part of this method is to find the maximal complete graph that meets the spatio-temporal constraints by indexing the graph. This method can be used to provide traffic analysis and route planning. In this paper, we make the following contributions:

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing