Local similarity detection algorithm for time series based on distributed architecture

doi:10.11772/j.issn.1001-9081.2016.12.3285

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (12): 3285-3291.DOI: 10.11772/j.issn.1001-9081.2016.12.3285

Previous Articles Next Articles

Local similarity detection algorithm for time series based on distributed architecture

LIN Yang, JIANG Yu'e, LIN Jie

Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China

Received:2016-06-22 Revised:2016-08-25 Online:2016-12-08 Published:2016-12-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61472082), the Natural Science Foundation of Fujian Province (2014J01220).LIN Yang, born in 1991, M. S. candidate. His research interests include time series, big data mining.

基于分布式架构的时间序列局部相似检测算法

林炀, 江育娥, 林劼

福建师范大学软件学院, 福州 350108

通讯作者: 林劼
作者简介:林炀(1991-),男,福建福州人,硕士研究生,主要研究方向:时间序列、大数据挖掘;江育娥(1970-),女,福建古田人,教授,博士,主要研究方向:数据挖掘;林劼(1972-),男,福建三明人,副教授,博士,主要研究方向:数据挖掘。
基金资助:
国家自然科学基金资助项目（61472082）；福建省自然科学基金资助项目（2014J01220）。

Abstract

Abstract: The CrossMatch algorithm based on the idea of Dynamic Time Warping (DTW) can be used to solve the problems of local similarity between time series. However, due to the high complexity of time and space, large amounts of computing resources are required. Thus, it is almost impossible to be used for long sequences. To solve the above mentioned problems, a new algorithm for local similarity detection based on distributed platform was proposed. The proposed algorithm was a distributed solution for CrossMatch. The problem of insufficient computing resources including time and space requirement was solved. Firstly, the series should be splited and distributed on several nodes. Secondly, the local similarity of every node's own series was dealt with. Finally, the results would be merged and assembled in order to find the local similarity of series. The experimental results show that the accuracy between the proposed algorithm and the CrossMatch algorithm is similar, and the proposed algorithm uses less time. The improved distributed algorithm can not only solve the computation problem of long sequence of time series which can not be processed by a single machine, but also improve the running speed by increasing the number of parallel computing nodes.

Key words: Dynamic Time Warping (DTW), MapReduce, time series, local similarity, parallelization

摘要： 基于动态时间规整算法思想的CrossMatch算法可以用来解决序列间的部分相似问题，但是由于算法时间空间复杂度过高，需要消耗大量的计算资源，因此无法应用于长序列之间的计算。针对以上问题，提出了一个基于分布式平台上的时间序列局部相似性检测算法。将CrossMatch算法实现在了分布式框架上，解决了计算资源不足的问题。首先需要对序列进行切分，分别放置在不同的节点上；其次，各节点分别处理各自序列的相似部分；最后，通过对结果进行汇总并拼接，找出序列间的局部相似。实验结果表明，该算法在准确性上和CrossMatch相近，在时间上也有提升。改进后的分布式算法不仅解决了单机无法处理的长序列计算问题，而且可以通过增加并行计算节点数提高运行速度。

关键词: 动态时间规整, MapReduce, 时间序列, 局部相似性, 并行化

CLC Number:

LIN Yang, JIANG Yu'e, LIN Jie. Local similarity detection algorithm for time series based on distributed architecture[J]. Journal of Computer Applications, 2016, 36(12): 3285-3291.

林炀, 江育娥, 林劼. 基于分布式架构的时间序列局部相似检测算法[J]. 计算机应用, 2016, 36(12): 3285-3291.

References

[1] 张炜,范年柏,汪文佳.基于自适应遗传算法的股票预测模型研究[J].计算机工程与应用,2015,51(4):254-259.(ZHANG W, FAN N B, WANG W J. Stock prediction model research based on improved adaptive genetic algorithm[J]. Computer Engineering and Applications, 2015, 51(4):254-259.)
[2] 周治平,苗敏敏.改进的马氏距离动态时间规整手势认证方法[J].计算机应用,2015,35(5):1467-1470.(ZHOU Z P, MIAO M M. Dynamic time warping gesture authentication algorithm based on improved Mahalanobis distance[J]. Journal of Computer Applications, 2015, 35(5):1467-1470.)
[3] 纪丽珍,李鹏,李林,等.冠心病患者心脏电-机械活动时间序列的熵分析[J].计算机工程与应用,2016,52(10):265-270.(JI L Z, LI P, LI L, et al. Analysis of cardiac electro-mechanical time-series in patients with coronary artery disease based on entropy[J]. Computer Engineering and Applications, 2016, 52(10):265-270.)
[4] TEMME C, EBINGHAUS R, EINAX J W, et al. Time series analysis of long-term data sets of atmospheric mercury concentrations[J]. Analytical and Bioanalytical Chemistry, 2004, 380(3):493-501.
[5] 苑卫国,刘云.微博用户特征量增长规律研究[J].计算机研究与发展,2015,52(2):522-532.(YUAN W G, LIU Y. Growth law of user characteristics in microblog[J]. Journal of Computer Research and Development, 2015, 52(2):522-532.)
[6] 程习锋,万定生,王亚明.水文时间序列相似性查询优化算法[J].计算机工程与设计,2013,34(11):4046-4050.(CHENG X F, WAN D S, WANG Y M. Similarity search optimization algorithm in hydrological time series[J]. Computer Engineering and Design, 2013, 34(11):4046-4050.)
[7] 唐毅,刘卫宁,孙棣华,等.改进时间序列模型在高速公路短时交通流量预测中的应用[J].计算机应用研究,2015,32(1):146-149.(TANG Y, LIU W N, SUN D H, et al. Application of improved time series model in forecasting of short-term traffic flow for freeway[J]. Application Research of Computers, 2015, 32(1):146-149.)
[8] KEOGH E, KASETTY S. On the need for time series data mining benchmarks:a survey and empirical demonstration[J]. Data Mining and Knowledge Discovery, 2003, 7(4):349-371.
[9] BERNDT D J, CLIFFORD J. Finding patterns in time series:a dynamic programming approach[M]//Advances in Knowledge Discovery and Data Mining. Menlo Park, CA:American Association for Artificial Intelligence, 1996:229-248.
[10] 李正欣,张凤鸣,李克武,等.一种支持DTW距离的多元时间序列索引结构[J].软件学报,2014,25(3):560-575.(LI Z X, ZHANG F M, LI K W, et al. Index structure for multivariate time series under DTW distance metric[J]. Journal of Software, 2014, 25(3):560-575.)
[11] TOYODA M, SAKURAI Y. Discovery of cross-similarity in data streams[C]//Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2010:101-104.
[12] TOYODA M, SAKURAI Y, ISHIKAWA Y. Pattern discovery in data streams under the time warping distance[J]. The VLDB Journal, 2013, 22(3):295-318.
[13] KEOGH E, RATANAMAHATANA C A. Exact indexing of dynamic time warping[J]. Knowledge and information systems, 2005, 7(3):358-386.
[14] SAKOE H, CHIBA S. Dynamic programming algorithm optimization for spoken word recognition[J]. IEEE Transactions on Acoustics, Speech and Signal Processing, 1978, 26(1):43-49.
[15] ITAKURA F. Minimum prediction residual principle applied to speech recognition[J]. IEEE Transactions on Acoustics, Speech and Signal Processing, 1975, 23(1):67-72.
[16] SALVADOR S, CHAN P. Toward accurate dynamic time warping in linear time and space[J]. Intelligent Data Analysis, 2007, 11(5):561-580.
[17] KIM M S, KIM S W, SHIN M. Optimization of subsequence matching under time warping in time-series databases[C]//SAC'05:Proceedings of the 2005 ACM Symposium on Applied Computing. New York:ACM, 2005:581-586.
[18] HONG Y, SHUQIANG Y, SHAODONG M, et al. A novel parallel scheme for fast similarity search in large time series[J]. China Communications, 2015, 12(2):129-140.

Local similarity detection algorithm for time series based on distributed architecture

基于分布式架构的时间序列局部相似检测算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Lilin FAN, Fukang CAO, Wanting WANG, Kai YANG, Zhaoyu SONG. Intermittent demand forecasting method based on adaptive matching of demand patterns [J]. Journal of Computer Applications, 2024, 44(9): 2747-2755.
[2]	Liting LI, Bei HUA, Ruozhou HE, Kuang XU. Multivariate time series prediction model based on decoupled attention mechanism [J]. Journal of Computer Applications, 2024, 44(9): 2732-2738.
[3]	Qinzhuang ZHAO, Hongye TAN. Time series causal inference method based on adaptive threshold learning [J]. Journal of Computer Applications, 2024, 44(9): 2660-2666.
[4]	Mei WANG, Xuesong SU, Jia LIU, Ruonan YIN, Shan HUANG. Time series classification method based on multi-scale cross-attention fusion in time-frequency domain [J]. Journal of Computer Applications, 2024, 44(6): 1842-1847.
[5]	Zixuan YUAN, Xiaoqing WENG, Ningzhen GE. Early classification model of multivariate time series based on orthogonal locality preserving projection and cost optimization [J]. Journal of Computer Applications, 2024, 44(6): 1832-1841.
[6]	Zexin XU, Lei YANG, Kangshun LI. Shorter long-sequence time series forecasting model [J]. Journal of Computer Applications, 2024, 44(6): 1824-1831.
[7]	Hongtao SONG, Jiangsheng YU, Qilong HAN. Industrial multivariate time series data quality assessment method [J]. Journal of Computer Applications, 2024, 44(6): 1743-1750.
[8]	Fan MENG, Qunli YANG, Jing HUO, Xinkuan WANG. EraseMTS： iterative active multivariable time series anomaly detection algorithm based on margin anomaly candidate set [J]. Journal of Computer Applications, 2024, 44(5): 1458-1463.
[9]	Shuai REN, Yuanfa JI, Xiyan SUN, Zhaochuan WEI, Zian LIN. Prediction of landslide displacement based on improved grey wolf optimizer and support vector regression [J]. Journal of Computer Applications, 2024, 44(3): 972-982.
[10]	Yiyang FAN, Yang ZHANG, Shang ZENG, Yu ZENG, Maoli FU. Multivariate long-term series forecasting model based on decomposition and frequency domain feature extraction [J]. Journal of Computer Applications, 2024, 44(11): 3442-3448.
[11]	Pei ZHAO, Yan QIAO, Rongyao HU, Xinyu YUAN, Minyue LI, Benchu ZHANG. Multivariate time series anomaly detection based on multi-domain feature extraction [J]. Journal of Computer Applications, 2024, 44(11): 3419-3426.
[12]	Yu ZENG, Yang ZHANG, Shang ZENG, Maoli FU, Qixue HE, Linlong ZENG. Time series prediction algorithm based on multi-scale gated dilated convolutional network [J]. Journal of Computer Applications, 2024, 44(11): 3427-3434.
[13]	Hui JIANG, Qiuyan YAN, Zhujun JIANG. Symmetric positive definite autoencoder method for multivariate time series anomaly detection [J]. Journal of Computer Applications, 2024, 44(10): 3294-3299.
[14]	Lishuo YE, Zhixue HE. Multiscale time series anomaly detection incorporating wavelet decomposition [J]. Journal of Computer Applications, 2024, 44(10): 3300-3306.
[15]	Li XU, Xiangyuan FU, Haoran LI. Spatial-temporal traffic flow prediction model based on gated convolution [J]. Journal of Computer Applications, 2023, 43(9): 2760-2765.