Monitoring Range Motif on Streaming Time-Series
Monitoring Range Motif on Streaming Time-Series
复制标题
DOI：
10.1007/978-3-319-98809-2_16
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
S. Kato;Daichi Amagata;Shunya Nishio;T. Hara
中科院分区：
文献类型：
--
作者：
S. Kato;Daichi Amagata;Shunya Nishio;T. Hara
最近基于物联网的应用程序以流方式生成时间序列，它们通常需要能够从生成的时间序列中进行环境监测和事件检测的技术。发现一个范围基序，即在时间序列中重复出现最多的子序列，是满足这一要求的一种有希望的方法。本文研究了基于计数的滑动窗口设置下流时间序列的范围母题监测问题。每当窗口滑动时，就会生成一个新的子序列，并删除最老的子序列。监视范围基序的一个直接解决方案是扫描窗口中的所有子序列，同时计算由相似性函数测量的它们的发生计数。由于主要的瓶颈是相似度计算，这种解决方案效率不高。因此，我们提出了一种有效的算法，即SRMM。SRMM很简单，它的时间复杂度基本上只取决于移除和生成的子序列的发生次数。我们使用四个真实数据集进行的实验表明，SRMM可以很好地扩展，并且表现出比基线更好的性能。
Recent IoT-based applications generate time-series in a streaming fashion, and they often require techniques that enable environmental monitoring and event detection from generated time-series. Discovering a range motif, which is a subsequence that repetitively appears the most in a time-series, is a promising approach for satisfying such a requirement. This paper tackles the problem of monitoring a range motif of a streaming time-series under a count-based sliding-window setting. Whenever a window slides, a new subsequence is generated and the oldest subsequence is removed. A straightforward solution for monitoring a range motif is to scan all subsequences in the window while computing their occurring counts measured by a similarity function. Because the main bottleneck is similarity computation, this solution is not efficient. We therefore propose an efficient algorithm, namely SRMM. SRMM is simple and its time complexity basically depends only on the occurring counts of the removed and generated subsequences. Our experiments using four real datasets demonstrate that SRMM scales well and shows better performance than a baseline.