Efficient Trajectory Clustering with Road Network Constraints Based on Spatiotemporal Buffering

Abstract

The analysis of individuals’ movement behaviors is an important area of research in geographic information sciences, with broad applications in smart mobility and transportation systems. Recent advances in information and communication technologies have enabled the collection of vast amounts of mobility data for investigating movement behaviors using trajectory data mining techniques. Trajectory clustering is one commonly used method, but most existing methods require a complete similarity matrix to quantify the similarities among users’ trajectories in the dataset. This creates a significant computational overhead for large datasets with many user trajectories. To address this complexity, an efficient clustering-based method for network constraint trajectories is proposed, which can help with transportation planning and reduce traffic congestion on roads. The proposed algorithm is based on spatiotemporal buffering and overlapping operations and involves the following steps: (i) Trajectory preprocessing, which uses an efficient map-matching algorithm to match trajectory points to the road network. (ii) Trajectory segmentation, where a Compressed Linear Reference (CLR) technique is used to convert the discrete 3D trajectories to 2D CLR space. (iii) Spatiotemporal proximity analysis, which calculates a partial similarity matrix using the Longest Common Subsequence similarity indicator in CLR space. (iv) Trajectory clustering, which uses density-based and hierarchical clustering approaches to cluster the trajectories. To verify the proposed clustering-based method, a case study is carried out using real trajectories from the GeoLife project of Microsoft Research Asia. The case study results demonstrate the effectiveness and efficiency of the proposed method compared with other state-of-the-art clustering-based methods.

Keywords

• spatiotemporal proximity analysis
• road network
• longest common subsequence
• movement behavior analysis
• geographic information sciences