论文标题
早期放弃pruneddtw及其在相似性搜索中的应用
Early Abandoning PrunedDTW and its application to similarity search
论文作者
论文摘要
动态时间翘曲（“ DTW”）距离在时间序列分析中广泛使用，无论是用于分类，聚类还是相似性搜索。但是，它的二次时间复杂性阻止了它的扩展。基于早期放弃DTW或完全跳过其计算的策略，由于某些用例（例如最近的邻居搜索）已开发出来。但是除了矢量化和近似值之外，直到最近引入了pruneddtw，dtw本身才没有提出任何进展。该算法能够修剪毫无疑问的一致性，后来又被安装了。我们提出了一个新版本的pruneddtw，“ eapruneddtw”，从一开始就考虑了早期放弃，并且能够比以前更快放弃。我们表明，EAPRUNEDDTW显着改善了UCR套件中相似性搜索的计算时间，并使降低界限可容纳。
The Dynamic Time Warping ("DTW") distance is widely used in time series analysis, be it for classification, clustering or similarity search. However, its quadratic time complexity prevents it from scaling. Strategies, based on early abandoning DTW or skipping its computation altogether thanks to lower bounds, have been developed for certain use cases such as nearest neighbour search. But vectorization and approximation aside, no advance was made on DTW itself until recently with the introduction of PrunedDTW. This algorithm, able to prune unpromising alignments, was later fitted with early abandoning. We present a new version of PrunedDTW, "EAPrunedDTW", designed with early abandon in mind from the start, and able to early abandon faster than before. We show that EAPrunedDTW significantly improves the computation time of similarity search in the UCR Suite, and renders lower bounds dispensable.
