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
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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)
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)
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)
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)
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)
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
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)
Pez, Y., Ez, I., Sheremetov, L.: A novel associative model for time series data mining. Pattern Recogn. Lett.41(1), 23–33 (2014)
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)
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)
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)
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)
Esling, P., Agon, C.: Time-scales data mining. ACM Computing Surveys (CSUR),45(1), 1–34, ACM (2015)
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
Hailin, L., Huichong, G.: Feature representing in data mining and similar distance measure in time series. Res. Comput. Appl.30(5), 1285–1291 (2013)
Junkui, L.: Research in time series similarity, Doctoral Dissertation, Huazhong University of Science and Technology (2008)
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
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)
Fu, W.C., Keogh, E., Lau, L.Y.: Scaling and time warping in time series querying. VLDB J.17(4), 899–921 (2008)
Bankó, Z., Abonyi, J.: Correlation based dynamic time warping of multivariate time series. Expert Syst. Appl.39(17), 12814–12823 (2012)
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
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)
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)
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)
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)
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)
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
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
- Yuan Yuan
You can also search for this author inPubMed Google Scholar
- Qibo Sun
You can also search for this author inPubMed Google Scholar
- Ao Zhou
You can also search for this author inPubMed Google Scholar
- Siyi Gao
You can also search for this author inPubMed Google Scholar
- Shangguang Wang
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toYuan Yuan.
Editor information
Editors and Affiliations
AGH University of Science and Technology, Krakow, Poland
Andrzej M.J. Skulimowski
University of Sussex, Brighton, UK
Zhengguo Sheng
Université de Versailles St Quentin, Versailles, France
Sondès Khemiri-Kallel
Université Paris 13, Villetaneuse, France
Christophe Cérin
National Chung Cheng University, Minxiong, Taiwan
Ching-Hsien Hsu
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
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
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-05080-1
Online ISBN:978-3-030-05081-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative