FTW: fast similarity search under the time warping distance

ABSTRACT

Time-series data naturally arise in countless domains, such as meteorology, astrophysics, geology, multimedia, and economics. Similarity search is very popular, and DTW (Dynamic Time Warping) is one of the two prevailing distance measures. Although DTW incurs a heavy computation cost, it provides scaling along the time axis. In this paper, we propose FTW (Fast search method for dynamic Time Warping), which guarantees no false dismissals in similarity query processing. FTW efficiently prunes a significant number of the search cost. Experiments on real and synthetic sequence data sets reveals that FTW is significantly faster than the best existing method, up to 222 times.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 5: Donald J. Berndt , James Clifford, Finding patterns in time series: a dynamic programming approach, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 6: S. Chu, E. Keogh, D. Hart, and M. Pazzani. Iterative deepening dynamic time warping for time series. In Proceedings of SIAM International Conference on Data Mining, 2002.
• 7: C. Faloutsos , H. Jagadish , A. Mendelzon , T. Milo, A Signature Technique for Similarity-Based Queries, Proceedings of the Compression and Complexity of Sequences 1997, p.2, June 11-13, 1997
• 8: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 9: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 10: R. W. Hamming. Digital Filters. Englewood Cliffs, N. J., 1977.
• 11: K. J. Jacob and D. Shasha. Fintime --- a financial time series benchmark. http://cs.nyu.edu/cs/faculty/shasha/fintime.html, March 2000.
• 12: Jyh-Shing Roger Jang , Hong-Ru Lee, Hierarchical filtering method for content-based music retrieval via acoustic input, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500201]
• 13: Hiroshi Kawasaki , Tomoyuki Yatabe , Katsushi Ikeuchi , Masao Sakauchi, Automatic modeling of a 3D city map from real-world video, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.11-18, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319465]
• 14: E. J. Keogh. Exact indexing of dynamic time warping. In Proceedings of VLDB, pages 406--417, August 2002.
• 15: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 16: E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Journal of Knowledge and Information Systems, pages 263--286, 2000.
• 17: Sang-Wook Kim , Sanghyun Park , Wesley W. Chu, An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases, Proceedings of the 17th International Conference on Data Engineering, p.607-614, April 02-06, 2001
• 18: Yang-Sae Moon , Kyu-Young Whang , Wook-Shin Han, General match: a subsequence matching method in time-series databases based on generalized windows, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564735]
• 19: D. W. Mount. Bioinfomatics: Sequence and Genome Analysis. Cold Spring Harbor, New York, 2000.
• 20: A. V. Oppenheim and R. W. Schafer. Digital Signal Processing. Englewood Cliffs, N. J., 1975.
• 21: Kazuhiro Otsuka , Tsutomu Horikoshi , Satoshi Suzuki , Haruhiko Kojima, Memory-Based Forecasting for Weather Image Patterns, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.330-336, July 30-August 03, 2000
• 22: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 23: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 24: Mladen Victor Wickerhauser, Adapted wavelet analysis from theory to software, A. K. Peters, Ltd., Natick, MA, 1994
• 25: Byoung-Kee Yi , Christos Faloutsos, Fast Time Sequence Indexing for Arbitrary Lp Norms, Proceedings of the 26th International Conference on Very Large Data Bases, p.385-394, September 10-14, 2000
• 26: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998
• 27: Yunyue Zhu , Dennis Shasha, Warping indexes with envelope transforms for query by humming, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872780]