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