Ship Trajectory Segment Clustering Using KDTree-Accelerated Hausdorff Distance

Abstract

To address the high computational complexity (O(m2)) of the traditional Hausdorff distance in large-scale vessel trajectory segment clustering, this study proposes a KDTree (k-dimensional tree)-accelerated DBSCAN (Density-Based Spatial Clustering of Applications with Noise) method. AIS (Automatic Identification System) trajectories are first segmented based on time intervals, then converted to planar coordinates via UTM (Universal Transverse Mercator) projection. A KDTree index is introduced to reduce the Hausdorff distance per trajectory pair to O(m log m). Finally, DBSCAN clustering is performed on the precomputed distance matrix. Experiments using AIS data from Xiamen Port (15,441 raw points, 165 trajectory segments after preprocessing) show that, compared with the traditional double-loop method, the proposed method reduces distance matrix computation time from 400–580 seconds to 20–23 seconds—a speedup factor of 18–25×—while producing identical clustering results. The proposed method significantly improves computational efficiency without compromising clustering accuracy, providing effective support for large-scale vessel trajectory clustering.