首页|An Amortized O(1) Lower Bound for Dynamic Time Warping in Motif Discovery

An Amortized O(1) Lower Bound for Dynamic Time Warping in Motif Discovery

扫码查看
原文链接
  • NETL
  • NSTL
  • IEEE
Motif discovery is a critical operation for analyzing series data in many applications. Recent works demonstrate the importance of finding motifs with Dynamic Time Warping. However, existing algorithms spend most of their time in computing lower bounds of Dynamic Time Warping to filter out the unpromising candidates. Specifically, the time complexity for computing these lower bounds is $O(L)$ for each pair of subsequences, where $L$ is the length of the motif (subsequences). This paper proposes two new lower bounds, called $LB_{f}$ and $LB_{M}$, both of them only cost amortized $O(1)$ time for each pair of subsequences. On real datasets, the proposed lower bounds are at least one magnitude faster than the state-of-the-art lower bounds used in motif discovery while still keeping satisfying effectiveness. Based on these faster lower bounds, this paper designs an efficient motif discovery algorithm that significantly reduces the cost of lower bounds. The experiments conducted on real datasets show the proposed algorithm is 5.6 times faster than the state-of-the-art algorithms on average.

Lower boundHeuristic algorithmsData miningComputer scienceEuclidean distanceElectronic mailTrainingTime measurementStandardsCosts

Zemin Chao、Hong Gao、Dongjing Miao、Jianzhong Li、Hongzhi Wang

展开 >

School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China

School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China|School of Computer Science and Technology, Zhejiang Normal University, Jinhua, China

School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China|China and Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China

2025

10.1109/TKDE.2025.3544751

IEEE transactions on knowledge and data engineering

IEEE transactions on knowledge and data engineering

ISSN：
年,卷(期)：2025.37(5)
  • 35