Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

An Acceleration Method for Similar Time-Series Finding

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNISA,volume 11253))

Included in the following conference series:

  • 1537Accesses

Abstract

Finding a time series subsequence that is similar to a specific time series is an important problem in trajectory data of vehicles analysis. The problem is made significantly harder for the massive and high-dimensional features of time series. The existing methods for finding the similar subsequences in time series have high time complexity and poor applicability to similar subsequence finding of different lengths. In this paper, we propose an acceleration method for similar time-series finding to address this issue. Firstly, our method defines and extracts the feature of the query sequence. Then, we use the feature as the key to search sequence with the same feature to form a candidate set. After that, in each sequence in candidate set, we filter the important points and add it into feature points list to hold the shape characteristics of original sequence better. Finally, Dynamic time warping (DTW) is used to find the similar time-series. Experiment results illustrate that the proposed method can improve the search efficiency and accuracy.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight 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

Similar content being viewed by others

References

  1. Agrawal, D., Das, S., Abbadi, A.: Big data and cloud computing: current state and future opportunities. In: Proceeding of the 14th International Conference on Extending Database Technology, pp. 530–533. ACM (2011)

    Google Scholar 

  2. Basu, S., Mukherjee, A., Klivansky, S.: Time series models for internet traffic. In: Fifteenth Joint Conference of the IEEE Computer Societies. NETWORKING the Next Generation, pp. 611–620. IEEE (1996)

    Google Scholar 

  3. Meesad, P., Tong, S.: Stock price time series prediction using neuro-fuzzy with support vector guideline system. In: ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/distributed Computing, pp. 422–427. IEEE Press (2008)

    Google Scholar 

  4. Fortuny, E.T.D., Smedt, T.D., Martens, D.: Evaluating and understanding text-based stock price prediction models. Inf. Process. Manage.50(2), 426–441 (2014)

    Article  Google Scholar 

  5. Ramos, C.M., Brito, Z.P., Kostov, B.: Google driven search for big data in autoimmune geo epidemiology: Analysis of 394,827 patients with systemic autoimmune diseases. Autoimmun. Rev.14(8), 670–679 (2015)

    Article  Google Scholar 

  6. Radha Krishna, P.: Big data search and mining. In: Mohanty, H., Bhuyan, P., Chenthati, D. (eds.) Big Data. SBD, vol. 11, pp. 93–120. Springer, New Delhi (2015).https://doi.org/10.1007/978-81-322-2494-5_4

    Chapter  Google Scholar 

  7. Leung, K.S., Mackinnon, R.K., Jiang, F.: Reducing the search space for big data mining for interesting patterns from uncertain data. In: IEEE International Congress on Big Data, Anchorage, pp. 315–322. IEEE Press (2014)

    Google Scholar 

  8. Pez, Y., Ez, I., Sheremetov, L.: A novel associative model for time series data mining. Pattern Recogn. Lett.41(1), 23–33 (2014)

    Google Scholar 

  9. Hu, B., Chen, Y., Zakaria, J.: Classification of multi-dimensional streaming time series by weighting each classifier’s track record. In: 2013 IEEE 13th International Conference on Data Mining, Texas, pp. 281–290. IEEE Press (2013)

    Google Scholar 

  10. Tataw, O.M., Rakthanmanon, T., Keogh, E.J.: Clustering of symbols using minimal description length. In: 12th International Conference on Document Analysis and Recognition, Washington, pp. 180–184, IEEE Press (2013)

    Google Scholar 

  11. Mennitt, D.J., Fristrup, K.: Anomaly detection and other practical considerations for estimating acoustical metrics from time series data. J. Acoust. Soc. Am.140(4), 3424 (2016)

    Article  Google Scholar 

  12. Gharehbaghi, A., Ask, P., Babic, A.: A pattern recognition framework for detecting dynamic changes on cyclic time series. Pattern Recognit.48(3), 696–708 (2015)

    Article  Google Scholar 

  13. Esling, P., Agon, C.: Time-scales data mining. ACM Computing Surveys (CSUR),45(1), 1–34, ACM (2015)

    Google Scholar 

  14. Goldin, D.Q., Kanellakis, P.C.: On similarity queries for time-series data: Constraint specification and implementation. In: Montanari, U., Rossi, F. (eds.) CP 1995. LNCS, vol. 976, pp. 137–153. Springer, Heidelberg (1995).https://doi.org/10.1007/3-540-60299-2_9

    Chapter  Google Scholar 

  15. Hailin, L., Huichong, G.: Feature representing in data mining and similar distance measure in time series. Res. Comput. Appl.30(5), 1285–1291 (2013)

    Google Scholar 

  16. Junkui, L.: Research in time series similarity, Doctoral Dissertation, Huazhong University of Science and Technology (2008)

    Google Scholar 

  17. Agrawal, R., Faloutsos, C., Swami, A.: Efficient similarity search in sequence databases. In: Lomet, David B. (ed.) FODO 1993. LNCS, vol. 730, pp. 69–84. Springer, Heidelberg (1993).https://doi.org/10.1007/3-540-57301-1_5

    Chapter  Google Scholar 

  18. Hongbao, M., Fengming, Z.: Time series symbolization method based on feature point conversion. Comput. Eng., China Electron. Technol. Group Corporation.34(12), 61–63 (2008)

    Google Scholar 

  19. Fu, W.C., Keogh, E., Lau, L.Y.: Scaling and time warping in time series querying. VLDB J.17(4), 899–921 (2008)

    Article  Google Scholar 

  20. Bankó, Z., Abonyi, J.: Correlation based dynamic time warping of multivariate time series. Expert Syst. Appl.39(17), 12814–12823 (2012)

    Article  Google Scholar 

  21. Kremer, H., Günnemann, S., Ivanescu, A.-M., Assent, I., Seidl, T.: Efficient processing of multiple DTW queries in time series databases. In: Bayard Cushing, J., French, J., Bowers, S. (eds.) SSDBM 2011. LNCS, vol. 6809, pp. 150–167. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-22351-8_9

    Chapter  Google Scholar 

  22. Faloutsos, C., Ranganathan, M., Anolopoulos, Y.: Fast subsequence matching in time-series database. In: Proceedings of the 1994 ACM SIGMOD international conference on Management of data, pp. 419–429. ACM Press (1994)

    Google Scholar 

  23. Yi, B.K., Jagadishg, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: Data Engineering, 1998. Proceedings, 14th International Conference on Data Engineering, pp. 201–208, IEEE (1998)

    Google Scholar 

  24. Floratou, A., Tata, S., Patel, J.M.: Efficient and accurate discovery of patterns in sequence data sets. In: 2010 IEEE 26th International Conference on Data Engineering, pp. 1154–1168. IEEE (2011)

    Google Scholar 

  25. Skulimowski, A.M.J.: Reveiling complexity-related time-series features with the monotonic aggregation transform. In: IEEE, International Conference on TOOLS with Artificial Intelligence, pp. 694–700. IEEE (2014)

    Google Scholar 

  26. Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: KDD workshop, Washington, pp. 359–370. KDD Press (1994)

    Google Scholar 

Download references

Acknowledgment

This research is supported in part by NSFC (61571066, 61602054), and Beijing Natural Science Foundation under Grant No. 4174100 (BNSF, 4174100).

Author information

Authors and Affiliations

  1. The State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China

    Yuan Yuan, Qibo Sun, Ao Zhou, Siyi Gao & Shangguang Wang

Authors
  1. Yuan Yuan

    You can also search for this author inPubMed Google Scholar

  2. Qibo Sun

    You can also search for this author inPubMed Google Scholar

  3. Ao Zhou

    You can also search for this author inPubMed Google Scholar

  4. Siyi Gao

    You can also search for this author inPubMed Google Scholar

  5. Shangguang Wang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYuan Yuan.

Editor information

Editors and Affiliations

  1. AGH University of Science and Technology, Krakow, Poland

    Andrzej M.J. Skulimowski

  2. University of Sussex, Brighton, UK

    Zhengguo Sheng

  3. Université de Versailles St Quentin, Versailles, France

    Sondès Khemiri-Kallel

  4. Université Paris 13, Villetaneuse, France

    Christophe Cérin

  5. National Chung Cheng University, Minxiong, Taiwan

    Ching-Hsien Hsu

Rights and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yuan, Y., Sun, Q., Zhou, A., Gao, S., Wang, S. (2018). An Acceleration Method for Similar Time-Series Finding. In: Skulimowski, A., Sheng, Z., Khemiri-Kallel, S., Cérin, C., Hsu, CH. (eds) Internet of Vehicles. Technologies and Services Towards Smart City. IOV 2018. Lecture Notes in Computer Science(), vol 11253. Springer, Cham. https://doi.org/10.1007/978-3-030-05081-8_21

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight 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


[8]ページ先頭

©2009-2025 Movatter.jp