FastDTW: 具有线性时间和空间复杂度的快速动态时间规整（DTW）

简介：
FastDTW是一种高效计算动态时间规整(DTW)的算法，它能够在保证近似最优解的前提下，实现线性的时空复杂度，适用于大规模时间序列数据分析。 FastDTW 是一种近似的动态时间扭曲 (DTW) 算法，在时间和内存复杂度上相比标准 DTW 的 O(N^2) 要求有显著改进，提供接近最优的对齐结果且其复杂度为线性即 O(N)。该算法采用多级方法从低分辨率开始递归地投影解决方案，并逐步细化这些初始解。 FastDTW 用 Java 编写实现，在 JVM 堆大小不足以容纳成本矩阵时会自动切换到使用磁盘存储的成本矩阵。此外，还实现了其他替代方案如 Sakoe-Chiba Band、抽象和分段动态时间扭曲 (PDTW)，这些都是在相关论文中评估过的。 这是斯坦萨尔瓦多与菲利普陈在其论文《FastDTW：在线性时间和空间复杂度下实现准确的动态时间扭曲》里描述实验所使用的原始官方版本。