A Surrogate Ship Trajectory Construction Method for Efficient Similarity Measurement in AIS Data Clustering Analysis

Since the advent of Automatic Identification System (AIS) has opened opportunities for shipping data to be disseminated worldwide, trajectory clustering has seen increasing applications in maritime traffic pattern recognition, trajectory prediction, anomaly detection, and route planning. Trajectory similarity measurement is a central concept in ship trajectory clustering, where the majority of computational time is spent on similarity calculations. However, the exponentially growing volume of AIS messages has posed significant challenges to efficient processing, with popular trajectory simplification methods such as Douglas-Peucker (DP) algorithm showing limited effectiveness in improving trajectory similarity calculations. In this study, we propose a novel surrogate ship trajectory construction (SurTraC) method to reduce the complexity of similarity calculations, where the Geohash gridding technique is employed to aggregate spatially adjacent points. The method can generate an alternative sparse trajectory that uniformly and precisely represents the original one. A case study using one-week AIS data from Gulf of Finland indicates that SurTraC can effectively simplify the trajectory dataset while maintaining the entirety of the features. Compared to the DP-based methods proposed in previous research, a discussion from the perspectives of trajectory simplification, similarity measurement, and clustering demonstrates that SurTraC can significantly accelerate similarity measurement without compromising clustering performance.