Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the dtw-distance of two length-$n$ time series, however, requires $O(n^2)$ time, which is often too slow in applications. Therefore, many heuristics have been proposed to speed up the dtw computation. These are often based on approximating or bounding the true dtw-distance or considering special inputs (e.g. binary or piecewise constant time series). In this paper, we present a fast and exact algorithm to compute the dtw-distance of two run-length encoded time series. This might be used for fast and accurate indexing and classification of time series in combination with preprocessing techniques such as piecewise aggregate approximation (PAA).


翻译:动态时间扭曲( DTW) 是时间序列中众所周知的相似度度量。 但是,计算两个长度-n美元时间序列的 dtw-距离的标准动态编程方法需要$O (n)2) 时间,这在应用中往往太慢。 因此,为了加速 dtw 计算,已经提出了许多超自然学方法。 这些方法往往基于对真正的 dtw- 距离的近似度或约束,或者考虑特殊输入( 如二进制或小巧的恒定时间序列 ) 。 在本文中,我们提出了一个快速和精确的算法来计算两个运行编码的时间序列的 dtw- 距离。 这可用于快速和准确的索引和时间序列分类, 与预处理技术如节纸总近似( PAAAA) 相结合 。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
143+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
LibRec 精选:你见过最有趣的论文标题是什么?
LibRec智能推荐
4+阅读 · 2019年11月6日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
5+阅读 · 2017年12月14日
Arxiv
3+阅读 · 2017年12月14日
Arxiv
3+阅读 · 2015年5月16日
VIP会员
相关VIP内容
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
143+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
相关资讯
LibRec 精选:你见过最有趣的论文标题是什么?
LibRec智能推荐
4+阅读 · 2019年11月6日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员