On the EDBT'23 paper "Spatial Structure-Aware Road Network Embedding via Graph Contrastive Learning":
In the published version of the paper, the following statement refers to the DTW technique [18], which has reported a linear computation time in practical applications [30]:
"We can reduce the time complexity of trajectory similarity computation to linear time by directly comparing the embeddings (e.g., with L1-norm), while traditional methods [5, 18] may need a quadratic time since they compute the distance between every pair of points on two trajectories."
[5] Helmut Alt and Michael Godau. 1995. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications 5, 01n02 (1995), 75-91.
[18] Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005. Exact indexing of dynamic time warping. Knowledge and Information Systems 7, 3 (2005), 358–386.
[30] Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. 2012. Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping. In KDD. 262–270.