Proceedings

All Common Subsequences

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 635-639.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Time series data abounds in real world problems. Measuring the similarity of time series is a key to solving these problems. One state of the art measure is the longest common subsequence. This measure advocates using the length of the longest common subsequence as an indication of similarity between sequences, but ignores information contained in the second, third, ..., longest subsequences. In order to capture the common information in sequences maximally we propose a novel measure of sequence similarity -- the number of all common subsequences. We show that this measure satisfies the common properties of similarity functions. Calculating this measure is not trivial as a brute force approach is exponential in time. We present a novel dynamic programming algorithm to calculate this number in polynomial time. We also suggest a different way of extending a class of such measures to multidimensional, real-valued time series, in the spirit of probabilistic metric spaces. We conducted an experimental study on the new similarity measure and the extension method for classification. It was found that both the new similarity and the extension method are consistently competitive.

  1. [Agrawal et al., 1995] 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 Proc. VLDB95, 1995.
  2. [Bergroth et al., 2000] L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In SPIRE'00: Proceedings of the Seventh In- ternational Symposium on String Processing Information Retrieval, page 39. IEEE Computer Society, 2000.
  3. [Das et al., 1997] G. Das, D. Gunopulos, and H. Mannila. Finding similar time series. In Proc. of PKDD97: Prin- ciples of Data Mining and Knowledge Discovery in Data- bases, pages 88-100, 1997.
  4. [Goldin et al., 2004] Dina Goldin, Todd Millstein, and Ayferi Kutlu. Bounded similarity querying for time-series data, 2004.
  5. [Gunopulos and Das, 2000] Dimitrios Gunopulos and Gau- tam Das. Time series similarity measures. 2000. Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining.
  6. [Hirschberg, 1977] Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of ACM, 24(4):664-675, 1977.
  7. [Hirschberg, 2005] Dan Hirschberg. Dynamic program- ming, 2005. http://www.ics.uci.edu/ ∼ dan/ class/161/notes/6/Dynamic.html. Link
  8. [Keogh and Folias, 2002] E. Keogh and T. Folias. The UCR time series data mining archive, 2002. http://www. cs.ucr.edu/ ∼ eamonn/TSDMA/index.html. Link
  9. [Keogh et al., 2004] Eamonn Keogh, Stefano Lonardi, and Chotirat Ann Ratanamahatana. Towards parameter-free data mining. In Proc. SIGKDD04, 2004.
  10. [Lin et al., 2005] Jessica Lin, Eamonn Keogh, and Stefano Lonardi. Visualizing and discovering non-trivial patterns in large time series databases. Information Visualization, 4(2):61-82, 2005.
  11. [Osborne and Bridge, 1997] Hugh Osborne and Derek Bridge. Models of similarity for case-based reasoning. In Procs. of the Interdisciplinary Workshop on Similarity and Categorisation, pages 173-179, 1997.
  12. [Schweizer and Sklar, 1983] B. Schweizer and A. Sklar. Probabilistic metric spaces. North-Holland, 1983.
  13. [Vlachos et al., 2003] Michail Vlachos, Marios Hadjieleft- heriou, Dimitrios Gunopulos, and Eamonn Keogh. Index- ing multi-dimensional time-series with support for mul- tiple distance measures. In Proceedings of SIGKDD03: ACM International Conference on Data Mining August 24-27, 2003, Washington, DC, USA, 2003.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards