Yasushi Sakurai
Masatoshi Yoshikawa
Christos Faloutsos
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.
- R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity search in sequence databases. In Proceedings of the 4th Conference on Foundations of Data Organization and Algorithms (FODO), pages 69--84, February 1993. Google Scholar
Digital Library
- R. Agrawal, K.-I. Lin, H. S. Sawhney, and K. Shim. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In Proceedings of VLDB, pages 490--501, September 1995. Google ScholarDigital Library
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of ACM SIGMOD, pages 322--331, May 1990. Google ScholarDigital Library
- S. Berchtold, C. Böhm, and H.-P. Kriegel. The pyramid-technique: Towards breaking the curse of dimensionality. In Proceedings of ACM SIGMOD, pages 142--153, June 1998. Google ScholarDigital Library
- D. J. Berndt and J. Clifford. Finding patterns in time series: A dynamic programming approach. In Advances in Knowledge Discovery and Data Mining, pages 229--248, AAAI/MIT, 1996. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- C. Faloutsos, H. V. Jagadish, A. O. Mendelzon, and T. Milo. A signature technique for similarity-based queries. In SEQUENCES, June 1997. Google ScholarDigital Library
- C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In Proceedings of ACM SIGMOD, pages 419--429, May 1994. Google ScholarDigital Library
- K. Fukunaga. Introduction to Statistical Pattern Recognition. Academic Press, 1990. Google ScholarDigital Library
- R. W. Hamming. Digital Filters. Englewood Cliffs, N. J., 1977.Google Scholar
- K. J. Jacob and D. Shasha. Fintime --- a financial time series benchmark. http://cs.nyu.edu/cs/faculty/shasha/fintime.html, March 2000. Google ScholarDigital Library
- J.-S. R. Jang and H.-R. Lee. Hierarchical filtering method for content-based music retrieval via acoustic input. In Proceedings of ACM Multimedia, pages 401--410, September/October 2001. Google ScholarDigital Library
- H. Kawasaki, T. Yatabe, K. Ikeuchi, and M. Sakauchi. Automatic modeling of a 3d city map from real-world video. In Proceedings of ACM Multimedia (1), pages 11--18, October/November 1999. Google ScholarDigital Library
- E. J. Keogh. Exact indexing of dynamic time warping. In Proceedings of VLDB, pages 406--417, August 2002. Google ScholarDigital Library
- E. J. Keogh, K. Chakrabarti, S. Mehrotra, and M. J. Pazzani. Locally adaptive dimensionality reduction for indexing large time series databases. In Proceedings of ACM SIGMOD, pages 151--162, May 2001. Google ScholarDigital Library
- 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.Google Scholar
- S.-W. Kim, S. Park, and W. W. Chu. An index-based approach for similarity search supporting time warping in large sequence databases. In Proceedings of ICDE, pages 607--614, April 2001. Google ScholarDigital Library
- Y.-S. Moon, K.-Y. Whang, and W.-S. Han. General match: a subsequence matching method in time-series databases based on generalized windows. In Proceedings of ACM SIGMOD, pages 382--393, June 2002. Google ScholarDigital Library
- D. W. Mount. Bioinfomatics: Sequence and Genome Analysis. Cold Spring Harbor, New York, 2000.Google Scholar
- A. V. Oppenheim and R. W. Schafer. Digital Signal Processing. Englewood Cliffs, N. J., 1975.Google Scholar
- K. Otsuka, T. Horikoshi, S. Suzuki, and H. Kojima. Memory-based forecasting for weather image patterns. In Proceedings of the 17th Conference on Artificial Intelligence (AAAI), pages 330--336, July 2000. Google ScholarDigital Library
- L. Rabiner and B.-H. Juang. Fundamentals of Speech Recognition. Englewood Cliffs, N. J., 1993. Google ScholarDigital Library
- R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of VLDB, pages 194--205, August 1998. Google ScholarDigital Library
- M. V. Wickerhauser. Adapted Wavelet Analysis from Theory to Software. A K Peters Ltd, Massachusetts, 1994. Google ScholarDigital Library
- B.-K. Yi and C. Faloutsos. Fast time sequence indexing for arbitrary lp norms. In Proceedings of VLDB, pages 385--394, September 2000. Google ScholarDigital Library
- B.-K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In Proceedings of ICDE, pages 201--208, February 1998. Google ScholarDigital Library
- Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In Proceedings of ACM SIGMOD, pages 181--192, June 2003. Google ScholarDigital Library
Recommendations
Similarity search for time series based on efficient warping measure
DM-IKM '12: Proceedings of the Data Mining and Intelligent Knowledge Management WorkshopSimilarity search is one of the most important tasks in time series data mining, and similarity measure between time series is a basic work. Dynamic time warping (DTW) is often used to compute distance between two time series by warping time axes to ...
Initialization of dynamic time warping using tree-based fast Nearest Neighbor
Initializing LBKeogh Dynamic Time Warping search using the Euclidean Distance Nearest Neighbor.Employing a fast Nearest Neighbor algorithm (fastNN) to increase computational efficiency.Successful application on five gesture datasets.Requiring about 20% ...
Fast k-Nearest Neighbor Searching in Static Objects
The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static ...
Comments