An algorithm on time series matching based on LB_Keogh and early abandon

作者：Cao Danyang^*; Liu Yinghua; Li Guangyuan; Liu Yongbin

来源：International Journal of Advancements in Computing Technology, 2012, 4(15): 280-286.

DOI：10.4156/ijact.vol4.issue 15.32

• Algorithm efficiency
• DTW
• Dynamic time warping distance
• Early abandon
• Euclidean distance
• Exact calculations
• Global constraints
• LB_keogh
• Lower bounds
• Matching algorithm
• Measure function
• Process time
• Running efficiency
• Sequence set

Euclidean distance can't process time warping, demand the sequences with the same length, and is sensitive for mutations of time series. Although dynamic time warping distance can avoid the faults of Euclidean distance, its computational complexity is higher. In order to improve the speed of searching the sequence set, LB_Keogh lower bound function is used to prune the candidate set. On this basis, the EA_DTW distance is adopted as a measure function, to improve the efficiency of the exact calculation of dynamic time warping distance. In order to obtain better running efficiency, this paper proposes a time series matching algorithm based on LB_Keogh and early abandon under global constraint. The simulation results show that the algorithm efficiency has been improved obviously when threshold Ε is smaller.

• 出版日期2012
• 单位北京大学