Vehicle Trajectory Analysis

Guo D., S. Liu, and H. Jin (2010). "A Graph-based Approach to Vehicle Trajectory Analysis", Journal of Location Based Service, 4(3), pages 183-199. You may download the paper from the journal website.

Abstract: It is difficult to extract meaningful patterns from massive trajectory data. One of the main challenges is to characterize, compare, and generalize trajectories to find overall patterns and trends. This research proposes a graph-based approach that converts trajectory data to a graph based representation, treats it as a complex network, and detects hidden community structures that can help characterize trajectories. 

The major limitation of existing methods is that they do not consider topological relations among trajectories. This research proposes a graph-based approach that treat trajectories as a complex network. Within the context of vehicle movements, the research develops a sequence of steps to extract representative points to reduce data redundancy, interpolate trajectories to accurately establish topological relationships among trajectories and locations, construct a graph (or matrix) representation of trajectories, apply a spatially constrained graph partitioning method to discover natural regions defined by trajectories, and use the discovered regions to search and visualize trajectory clusters. Applications with a real data set shows that out new approach can effectively facilitate the understanding of spatial and spatiotemporal patterns in trajectories and discover novel patterns that existing methods cannot find.

Keywords: trajectory analysis; interpolation; clustering, regionalization, graph partitioning, data mining



Figure 4: Hierarchical regions derived with spatially constrained graph partitioning. The two maps show the regions at different hierarchical levels: two regions (left map) and 10 regions (right map).

 

Figure 5: Trajectory clustering with 2 regions. It simply calculates the portion of each trajectory in the south region (since there are only two regions). The blue cluster (top-right map) has 94 trajectories, the major portion (>90%) of each is within the north region. The red cluster (bottom-left map) contains 136 trajectories. Only 46 trajectories involve both regions significantly (bottom-right map).

 

Figure 6: Selected clusters that are defined with 10 regions. Each cluster involves a different subset of the 10 regions.

 

Guo D., S. Liu, and H. Jin (2010). "A Graph-based Approach to Vehicle Trajectory Analysis", Journal of Location Based Service (JLBS), 4(3) 183-199.