Abstract

This paper presents a brief review on the lower bounding(LB) methods applied on Dynamic Time Warping(DTW) till now. Apart from providing a survey on the methods, an attempt has been made to compare these methods in terms of constraints involved with these methods. Some Lower Bounding (LB) methods have better pruning power than others, some are better in terms of running time and also there are some which do introduce greater number of false dismissals than others. This work will help researchers in selecting a suitable lower bounding method for their application. The authors hope that this work will provide a scope of evaluating Lower bounding distances of DTW in the area of speech recognition and verification in general and will also help identify research topic and application in this area.

References

• Yi B, Jagadish K, Faloutsos H (1998) Efficient retrieval of similar time sequences under time warping. In ICDE 98, pp 23–27.
• Kim S, Park S, Chu W (2001) An index-based approach for similarity search supporting time warping in large sequence databases. In: Proceedings of the 17th international conference on data engineering, pp 607–614.
• Keogh, E. 2002. Exact indexing of dynamic time warping. In Proceedings of 28th International Conference on Very Large Data Bases, Hong Kong, 406-417.
• Faloutsos C, Lin K (1995) FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. SIGMOD conference, pp 163–174
• Sakurai, Y. , Yoshikawa, M. , and Faloutsos, C. 2005. FTW: Fast Similarity Search under the Time Warping. In Proceedings of PODS '05, 326-337.
• Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In SIGMOD Conference, pages 181–192, 2003.
• N. Beckmann, H. Kriegel, R. Schneider, B. Seeger, The R*-tree: an efficient and robust access method for points and rectangles, SIGMOD '90 (1990) 322-331.
• Itakura, Minimum prediction residual principle applied to speech recognition, IEEE Transactions on Acoustics, Speech, and Signal Processing 23 (1) (1975)67-72.
• M. Zhou, M. H. Wong, Boundary-based lower-bound functions for Dynamic Time Warping and their indexing, ICDE 2007 (2007) 1307-1311.
• Lemire, D. Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound. Pattern Recognition 42 (9) , 2169-2180, 2009.
• Park S, Chu W, Yoon J, Hsu C (2000) Efficient searches for similar subsequences of different lengths in sequence databases. In: Proceedings of the 16th IEEE international conference on data engineering, pp 23–32.
• H. R. Lee, C. Chen, J. R. Jang (2005) Approximate lower-bounding functions for the speedup of DTW for melody recognition,pp 178-181.
• N. C. Thuong and D. T. Anh,(2012) Comparing three Lower Bounding Methods for DTW inTime Series Classification: Proceedings of the Third Symposium on Information and Communication Technology,pp 200-206.
• Berndt D, Clifford J (1994) Using dynamic time warping to find patterns in time series. AAAI-94 workshop on knowledge discovery in databases, pp 229–248
• Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoustics Speech Signal Process ASSP 26,pp 43–49.