Extensible Lower Bound Function for Dynamic Time Warping

摘要

The similarity measurement of time series is a significant approach to mine the rich and valuable law information hidden in the massive time series data. As the most advantageous approach in measuring similarities of time series, Dynamic Time Warping (DTW) has become one of the hottest researches in the field of data mining. However, the DTW algorithm does not satisfy the trigonometric inequality, its time and space complexity are extremely high, how to efficiently realize the retrieval of similar sequences in large-scale sequential sequences remains a challenge. This paper first introduces a novel extensible lower bound function (LB_ex), then validates the effeteness of its lower bound tightness theoretically, finally uses a bidirectional processing strategy (BPS) to reduce computation complexity and time consumption during the massive sequential data retrieval, and significantly improves the operation efficiency. Extensive experiments were conducted with public dataset to evaluate feasibility and efficiency of the proposed approaches. The results show that LB_ex and BPS performs a more robust and efficient processing of similarity of time series than does traditional approaches, reducing by about 43% of time-consuming.