Exact Discovery of Time Series Motifs.
Exact Discovery of Time Series Motifs.
复制标题
DOI：
10.1137/1.9781611972795.41
复制
发表时间：
2009-01-01
期刊：
影响因子：
--
通讯作者：
Westover, Brandon
中科院分区：
文献类型：
--
作者：
Mueen, Abdullah;Keogh, Eamonn;Westover, Brandon
时间序列主题是成对的单个时间序列，或较长时间序列的子序列，它们彼此非常相似。就像它们在计算生物学中的离散类似物一样，这种相似性暗示了由于某种原因而被保守的结构，因此可能会引起人们的兴趣。自2002年时间序列模体形式化以来，数十名研究人员将其用于许多不同领域的不同应用。由于计算基序的明显算法在项数上是二次的，因此文献中已经提出了十几种发现基序的近似算法。在这项工作中，我们首次提出了一种易于处理的精确算法来寻找时间序列模体。正如我们将通过广泛的实验证明的那样，我们的算法在大数据集中比蛮力搜索快三个数量级。我们进一步证明了我们的算法足够快，可以作为高级数据挖掘算法中的一个子例程，用于随时分类、近重复检测和摘要，并考虑了从脑电图仪解释到昆虫学遥测数据挖掘等领域的详细案例研究。
Time series motifs are pairs of individual time series, or subsequences of a longer time series, which are very similar to each other. As with their discrete analogues in computational biology, this similarity hints at structure which has been conserved for some reason and may therefore be of interest. Since the formalism of time series motifs in 2002, dozens of researchers have used them for diverse applications in many different domains. Because the obvious algorithm for computing motifs is quadratic in the number of items, more than a dozen approximate algorithms to discover motifs have been proposed in the literature. In this work, for the first time, we show a tractable exact algorithm to find time series motifs. As we shall show through extensive experiments, our algorithm is up to three orders of magnitude faster than brute-force search in large datasets. We further show that our algorithm is fast enough to be used as a subroutine in higher level data mining algorithms for anytime classification, near-duplicate detection and summarization, and we consider detailed case studies in domains as diverse as electroencephalograph interpretation and entomological telemetry data mining.