Skip to main content
SpringerLink
Log in

Alignment of Time Series for Subsequence-to-Subsequence Time Series Matching

  • Conference paper
  • First Online:
Intelligent Systems in Science and Information 2014 (SAI 2014)

Part of the book series: Studies in Computational Intelligence ((SCI,volume 591))

Included in the following conference series:

Abstract

The success of time series data mining applications, such as query by content, clustering, and classification, is greatly determined by the performance of the algorithm used for the determination of similarity between two time series. The previous research on time series matching has mainly focused on whole sequence matching and to limited extent on sequence-to-subsequence matching. Relatively, very little work has been done on subsequence-to-subsequence matching, where two time series are considered similar if they contain similar subsequences or patterns in the same time order. This paper presents an effective approach capable of handling whole sequence, sequence-to-subsequence and subsequence-to-subsequence matching. The proposed approach derives its strength from the novel two stage segmentation algorithm, which facilitates the alignment of the two time series by retaining perceptually important points of the two time series as break points.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Esling, P., Agon, C.: Time-series data mining. ACM Comput. Surv. 45, 34 (2012)

    Google Scholar 

  2. Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E.: Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. Very Large Databases 1, 1542–1552 (2008)

    Google Scholar 

  3. Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: KDD Workshop, pp. 359–370. AAAI Press, Palo Alto (1994)

    Google Scholar 

  4. Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Sig. Proc. 26(1), 43–49 (1978)

    Article  MATH  Google Scholar 

  5. Morse, M.D., Patel, J.M.: An efficient and accurate method for evaluating time series similarity. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 569–580 (2007)

    Google Scholar 

  6. Athitsos, V., Papapetrou, P., Potamias, M., Kollios, G., Gunopulos, D.: Approximate embedding-based subsequence matching of time series. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 365–378 (2008)

    Google Scholar 

  7. Park, S., Kim, S., Chu, W.W.: Segment-based approach for subsequence searches in sequence databases. In: Symposium on Applied Computing, pp. 248–252 (2001)

    Google Scholar 

  8. Zhu, Y., Shasha, D.: Warping indexes with envelope transforms for query by humming. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 181–192 (2003)

    Google Scholar 

  9. Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast subsequence matching in time-series databases. In: Snodgrass, R.T., Winslett, M. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 19–429 (1994)

    Google Scholar 

  10. Wu, Y., Agrawal, D., Abbadi, A.E.: A comparison of DFT and DWT based similarity search in time-series databases. In: Proceedings of the 9th International Conference on Information and Knowledge Management, pp. 488–495 (2000)

    Google Scholar 

  11. Hung, N.Q., Anh, D.T.: An improvement of PAA for dimensionality reduction in large time series databases. In: Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, pp. 698–707 (2008)

    Google Scholar 

  12. Keogh, E., Chakrabarti, K., Pazzani, M., Mehrotra, S.: Dimensionality reduction for fast similarity search in large time series databases. Knowl. Inf. Syst. 3, 263–286 (2001)

    Article  MATH  Google Scholar 

  13. Chakrabarti K, Keogh E, Mehrotra S, Pazzani M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. 27, 118–228

    Google Scholar 

  14. Keogh, E., Pazzani, M.: An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In: 4th International Conference on Knowledge Discovery and Data Mining, pp. 239–241 (1998)

    Google Scholar 

  15. Lin, J., Keogh, E., Wei, L., Lonardi, S.: Experiencing SAX: a novel symbolic representation of time series. Data Min. Knowl. Discov. 15, 107–144 (2007)

    Google Scholar 

  16. Lemire, D.: A better alternative to piecewise linear time series segmentation. In: SIAM Data Mining (2007)

    Google Scholar 

  17. Bettaiah, V., Ranganath, H.S.: An analysis of time series representation methods. In: Proceedings of the 2014 ACM Southeast Regional Conference, Article 16, p 6 (2014)

    Google Scholar 

  18. Bettaiah, V., Ranganath, H.S: Two stage segmentation for efficient time series matching. In: 2nd International Conference on Research in Science, Engineering and Technology, pp. 29–35 (2014)

    Google Scholar 

  19. Bettaiah, V., Ranganath, H.S: An effective subsequence-to-subsequence time series matching approach. In: Science and Information (SAI) Conference, pp. 112–122 (2014)

    Google Scholar 

  20. The UCR Time Series Classification/Clustering. http://www.cs.ucr.edu/eamonn/time_series_data/. Retrieved Aug 2013

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, The University of Alabama in Huntsville, 301 Sparkman Dr NW, Huntsville, AL, 35803, USA

    Vineetha Bettaiah & Heggere S. Ranganath

Authors
  1. Vineetha Bettaiah
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Heggere S. Ranganath
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vineetha Bettaiah .

Editor information

Editors and Affiliations

  1. Graduate School of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, London, United Kingdom

    Supriya Kapoor

  3. The Science and Information (SAI) Organization, London, United Kingdom

    Rahul Bhatia

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Bettaiah, V., Ranganath, H.S. (2015). Alignment of Time Series for Subsequence-to-Subsequence Time Series Matching. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Intelligent Systems in Science and Information 2014. SAI 2014. Studies in Computational Intelligence, vol 591. Springer, Cham. https://doi.org/10.1007/978-3-319-14654-6_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-14654-6_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-14653-9

  • Online ISBN: 978-3-319-14654-6

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation