论文标题
FastDTW近似且通常比算法慢得多。
FastDTW is approximate and Generally Slower than the Algorithm it Approximates
论文作者
论文摘要
许多时间序列数据挖掘问题可以通过重复使用距离度量来解决。此类任务的示例包括相似性搜索，聚类，分类，异常检测和分割。在过去的二十年中，人们已经知道，在大多数域中，动态时间扭曲（DTW）距离度量是用于大多数任务的最佳措施。由于经典的DTW算法具有二次时间的复杂性，因此引入了许多想法，以减少其摊销时间或快速近似它。最引用的近似方法之一是FastDTW。 FastDTW算法已有一千多个引用，并已在数百项研究工作中明确使用。在这项工作中，我们提出了令人惊讶的主张。在任何现实的数据挖掘应用程序中，近似FastDTW都比确切的DTW慢得多。这个事实显然对使用此算法的社区具有影响：允许其解决更大的数据集，获得确切的结果并在更少的时间内完成。
Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time.
