Pattern discovery in data streams under the time warping distance
Pattern discovery in data streams under the time warping distance
复制标题
DOI：
10.1007/s00778-012-0289-3
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Machiko Toyoda;Yasushi Sakurai;Y. Ishikawa
中科院分区：
文献类型：
--
作者：
Machiko Toyoda;Yasushi Sakurai;Y. Ishikawa
子序列匹配是数据流挖掘领域的一个基本问题。近年来，已经有大量的研究工作花费在有效地找到相似的查询序列的连续性。与子序列匹配相关的另一个挑战性问题是，当两个序列都在演变时，我们如何识别共同的局部模式。这个问题出现在趋势检测、聚类和离群值检测中。动态时间规整（DTW）通常用于子序列匹配，并且是一种强大的相似性度量。然而，使用DTW的直接方法对于该问题产生高计算成本。在本文中，我们提出了一个一遍算法，交叉匹配，实现上述目标。交叉匹配解决了两个重要的挑战：（1）我们如何有效地识别共同的本地模式，而没有任何遗漏？(2)我们如何在数据流处理中找到共同的局部模式？为了解决这些挑战，CrossMatch结合了三个想法：（1）评分函数，它间接计算DTW距离以降低计算成本，（2）位置矩阵，它存储起始位置，以流式方式跟踪常见的本地模式，以及（3）流式算法，它有效地识别常见的本地模式并将其动态输出。我们提供了一个理论分析，并证明我们的算法不牺牲准确性。我们的实验评估和案例研究表明，CrossMatch可以在恒定的时间（每次更新）和空间内逐步发现数据流中的常见局部模式。
Subsequence matching is a basic problem in the field of data stream mining. In recent years, there has been significant research effort spent on efficiently finding subsequences similar to a query sequence. Another challenging issue in relation to subsequence matching is how we identify common local patterns when both sequences are evolving. This problem arises in trend detection, clustering, and outlier detection. Dynamic time warping (DTW) is often used for subsequence matching and is a powerful similarity measure. However, the straightforward method using DTW incurs a high computation cost for this problem. In this paper, we propose a one-pass algorithm, CrossMatch, that achieves the above goal. CrossMatch addresses two important challenges: (1) how can we identify common local patterns efficiently without any omission? (2) how can we find common local patterns in data stream processing? To tackle these challenges, CrossMatch incorporates three ideas: (1) a scoring function, which computes the DTW distance indirectly to reduce the computation cost, (2) a position matrix, which stores starting positions to keep track of common local patterns in a streaming fashion, and (3) a streaming algorithm, which identifies common local patterns efficiently and outputs them on the fly. We provide a theoretical analysis and prove that our algorithm does not sacrifice accuracy. Our experimental evaluation and case studies show that CrossMatch can incrementally discover common local patterns in data streams within constant time (per update) and space.