This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
teaching:projh402 [2021/09/18 18:32] ezimanyi [Dynamic Time Warping for Trajectories] |
teaching:projh402 [2021/09/19 10:51] ezimanyi [Dynamic Time Warping for Trajectories] |
||
|---|---|---|---|
| Line 79: | Line 79: | ||
| Links: | Links: | ||
| - | * {{:teaching:symbolic_trajectories.pdf|}} | + | * R.H. Guting, F Valdés, M.L. Damiani, {{:teaching:symbolic_trajectories.pdf|Symbolic Trajectories}}, ACM Transactions on Spatial Algorithms Systems, (1)2, Article 7, 2015 |
| ===== Trajectory Data Warehouses ===== | ===== Trajectory Data Warehouses ===== | ||
| Line 110: | Line 111: | ||
| ===== Dynamic Time Warping for Trajectories ===== | ===== Dynamic Time Warping for Trajectories ===== | ||
| - | The dynamic time warping (DTW) algorithm is able to find the optimal alignment between two time series. It is often used to determine time series similarity, classification, and to find corresponding regions between two time series. Several dynamic time warping implementations are available. However, DTW has a quadratic time and space complexity that limits its use to small time series data sets. Therefore, a fast approximation of DTW have been proposed that has linear time and space complexity. | + | The dynamic time warping (DTW) algorithm is able to find the optimal alignment between two time series. It is often used to determine time series similarity, classification, and to find corresponding regions between two time series. Several dynamic time warping implementations are available. However, DTW has a quadratic time and space complexity that limits its use to small time series data sets. Therefore, a fast approximation of DTW that has linear time and space complexity has been proposed. |
| The goal of this project is to survey and to prototype in MobilityDB the state of art methods in dynamic time warping. | The goal of this project is to survey and to prototype in MobilityDB the state of art methods in dynamic time warping. | ||
| - | * Toni Giorgino, [[https://www.jstatsoft.org/article/view/v031i07|Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package]] | + | * T. Giorgino, [[https://www.jstatsoft.org/article/view/v031i07|Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package]], Journal of Statistical Software, (31)7, 2009. |
| - | * S. Salvador, P. Chan [[https://cs.fit.edu/~pkc/papers/tdm04.pdf|FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space]] | + | * S. Salvador, P. Chan, [[https://cs.fit.edu/~pkc/papers/tdm04.pdf|FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space]], Intelligent Data Analysis, 11(5):561-580, 2007. |
| + | * D.F. Silva, G.E.A.P.A. Batista, [[http://sites.labic.icmc.usp.br/dfs/pdf/SDM_PrunedDTW.pdf|Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation]], Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 837-845, 2016. | ||
| + | * G. Al-Naymat, S. Chawla, J. Taheri (2012). [[https://arxiv.org/abs/1201.2969|SparseDTW: A Novel Approach to Speed up Dynamic Time Warping]]. CoRR abs/1201.2969, 2012. | ||
| + | * M. Müller, H. Mattes, F. Kurth, [[https://www.audiolabs-erlangen.de/content/05-fau/professor/00-mueller/03-publications/2006_MuellerMattesKurth_MultiscaleAudioSynchronization_ISMIR.pdf|An Efficient Multiscale Approach to Audio Synchronization]]. Proceedings of the International Conference on Music Information Retrieval (ISMIR), pp. 192-197, 2006. | ||
| + | * Thomas Prätzlich, Jonathan Driedger, and Meinard Müller, [[https://www.researchgate.net/publication/303667579_Memory-Restricted_Multiscale_Dynamic_Time_Warping|Memory-Restricted Multiscale Dynamic Time Warping]], Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 569-573, 2016. | ||
| ===== Geospatial Trajectory Similarity Measure ===== | ===== Geospatial Trajectory Similarity Measure ===== | ||
| One of the main functions for a wide range of application domains is to measure the similarity between two moving objects' trajectories. This is desirable for similarity-based retrieval, classification, clustering and other querying and mining tasks over moving objects' data. The existing movement similarity measures can be classified into two classes: (1) spatial similarity that focuses on finding trajectories with similar geometric shapes, ignoring the temporal dimension; and (2) spatio-temporal similarity that takes into account both the spatial and the temporal dimensions of movement data. | One of the main functions for a wide range of application domains is to measure the similarity between two moving objects' trajectories. This is desirable for similarity-based retrieval, classification, clustering and other querying and mining tasks over moving objects' data. The existing movement similarity measures can be classified into two classes: (1) spatial similarity that focuses on finding trajectories with similar geometric shapes, ignoring the temporal dimension; and (2) spatio-temporal similarity that takes into account both the spatial and the temporal dimensions of movement data. | ||