Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping
Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping
复制标题
DOI：
10.1145/2500489
复制
发表时间：
2013-09-01
影响因子：
3.6
通讯作者：
Keogh, Eamonn
中科院分区：
文献类型：
--
作者：
Rakthanmanon, Thanawin;Campana, Bilson;Keogh, Eamonn
大多数时间序列数据挖掘算法使用相似性搜索作为核心子程序，因此相似性搜索所花费的时间几乎是所有时间序列数据挖掘算法的瓶颈，包括分类，聚类，模体发现，异常检测，将搜索扩展到大型数据集的困难在很大程度上解释了为什么大多数关于时间序列数据挖掘的学术工作都停留在考虑数百万个时间序列对象，而许多工业和科学都有数十亿个时间序列对象等待探索。在这项工作中，我们表明，通过使用四个新颖的想法相结合，我们可以搜索和挖掘大量的时间序列的第一次。我们证明了以下不直观的事实：在大型数据集中，我们可以在动态时间弯曲（DTW）下精确搜索，比当前最先进的欧氏距离搜索算法快得多。我们展示了有史以来最大的一组时间序列实验。特别是，我们考虑的最大数据集大于所有已发表的数据挖掘论文中考虑的所有时间序列数据集的总和。我们解释了我们的想法如何使我们能够解决更高层次的时间序列数据挖掘问题，如主题发现和聚类的规模，否则是站不住脚的。此外，我们展示了我们的想法如何使我们能够有效地支持统一的缩放距离测度，这一测度的效用似乎被低估了，但我们在这里演示。除了挖掘多达1万亿个数据点的大规模数据集外，我们还将展示我们的想法对数据流的实时监控也有影响，使我们能够处理更快的到达率和/或使用比目前更便宜和更低功率的设备。
Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms, including classification, clustering, motif discovery, anomaly detection, and so on. The difficulty of scaling a search to large datasets explains to a great extent why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine massive time series for the first time. We demonstrate the following unintuitive fact: in large datasets we can exactly search under Dynamic Time Warping (DTW) much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We explain how our ideas allow us to solve higher-level time series data mining problems such as motif discovery and clustering at scales that would otherwise be untenable. Moreover, we show how our ideas allow us to efficiently support the uniform scaling distance measure, a measure whose utility seems to be underappreciated, but which we demonstrate here. In addition to mining massive datasets with up to one trillion datapoints, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.