Tight lower bounds for dynamic time warping. (July 2021)

• Record Type: Journal Article
• Authors: Webb, Geoffrey I.; Petitjean, François
• Is Part Of: Pattern recognition. Volume 115(2021)
• Publication Date: 2021-07
• Subjects: Dynamic time warping -- Lower bound -- Time series; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.107895
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Four novel and effective lower bounds for Dynamic Time Warping that have linear complexity. Provide substantial speed-up for nearest neighbor time series search. Useful under a wide variety of different types of nearest neighbour search. Abstract: Dynamic Time Warping ( DTW ) is a popular similarity measure for aligning and comparing time series. Due to DTW 's high computation time, lower bounds are often employed to screen poor matches. Many alternative lower bounds have been proposed, providing a range of different trade-offs between tightness and computational efficiency. LB _ KEOGH provides a useful trade-off in many applications. Two recent lower bounds, LB _ IMPROVED and LB _ ENHANCED, are substantially tighter than LB _ KEOGH . All three have the same worst case computational complexity—linear with respect to series length and constant with respect to window size. We present four new DTW lower bounds in the same complexity class. LB _ PETITJEAN is substantially tighter than LB _ IMPROVED, with only modest additional computational overhead. LB _ WEBB is more efficient than LB _ IMPROVED, while often providing a tighter bound. LB _ WEBB is always tighter than LB _ KEOGH . The parameter free LB _ WEBB is usually tighter than LB _ ENHANCED . A parameterized variant, LB_Webb_Enhanced, is always tighter than LB _ ENHANCED . A further variant, LB _ WEBB *, is useful for some constrained distance functions. In extensive experiments, LB _ WEBB proves to be very effective for nearest neighbor search.