With the rapid development of the global economy, transport safety and security have become the key issues in maritime transportation all over the world. In practical applications, the Automatic Identification System (AIS)-based measurement of similarities between different vessel trajectories plays an important role in improving maritime transportation, e.g., maritime navigation, maritime supervision and management. However, the received AIS datasets are usually composed of a large amount of redundant information which could significantly increase the computational complexity. To deal with this problem, a Douglas-Peucker (DP)-based calculation method is introduced in this paper to accurately compress the spatio-temporal AIS trajectories while preserving the main geometrical structures. Based on the compressed trajectories, it is able to accelerate the Dynamic Time Warping (DTW) algorithm for the measurement of similarities between different vessel trajectories. In particular, the combination of DP and DTW has the capacity of significantly reducing the computational cost and guaranteeing the accuracy of similarity measures. The experimental results have demonstrated the superior performance of the proposed method in terms of computational cost and accuracy of similarity measures.