Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (10): 247-260.doi: 10.11896/jsjkx.230800146

• Database & Big Data & Data Science • Previous Articles     Next Articles

All-chain Sets Mining Algorithm for Multi-scale Nearest Time Series

WANG Shaopeng1,2,3,4, FENG Chunkai1   

  1. 1 School of Software Engineering,Inner Mongolia University,Hohhot 010021,China
    2 Inner Mongolia Engineering Research Center of Ecological Big Data Ministry of Education,Hohhot,010021,China
    3 Inner Mongolia Engineering Laboratory for Cloud Computing and Service,Hohhot 010021,China
    4 Inner Mongolia Discipline Inspection and Supervision Big Data Laboratory,Hohhot 010021,China
  • Received:2023-08-22 Revised:2023-09-22 Online:2024-10-15 Published:2024-10-11
  • About author:WANG Shaopeng,born in 1984,Ph.D, associate professor,master supervisor,is a member of CCF(No.26971M).His main research interests include big data mining,spatio-temporal big data processing and analyzing,convergence of AI and DB.
  • Supported by:
    National Natural Science Foundation of China(62066034,62262047),Inner Mongolia Science & Technology Plan(61862047) and Inner Mongolia Discipline Inspection and Supervision Big Data Laboratory Open Project Fund(IMDBD2020011).

PDF (PC)

250

Abstract: Mining all-chain set in the time series is an emerging area.To the best of our knowledge,no method has been proposed to mining all-chain sets over multi-scale nearest time series.In this paper,the problem of mining all-chain sets over multi-scale nearest time series is focused.The mining problem of all-chain sets over multi-scale nearest time series is studied,and a mining algorithm with incremental computation characteristics is proposed on the basis of the existing LRSTOMP and ALLC algorithms,MTSC(mining time series all-chain sets over multi-scale nearest time series).The MTSC algorithm uses the LRSTOMP and ALLC algorithms sequentially to process the content of the 1st nearest time series member to obtain the mining results of all-chain sets over this member,while keeping the PL and PR structures associated with this member.Starting from the 2nd nearest time series member,the LRSTOMP process in the MTSC algorithm only needs to deal with the additions of the current nearest time series member with respect to the previous nearest time series member,and further combining the PL and PR on the pre-vious nearest time series member can incrementally obtain the structure of the PL and PR on the current nearest time series member,and based on which the ALLC algorithm is used to get the all-chain set mining result on that member.Compared to the Naive way using LRSTOMP and ALLC algorithms to process the content of each recent time series member,the MTSC algorithm avoids repetitive computation on all data by utilizing the idea of incremental computation,which improves the execution speed of the algorithm and has better time efficiency.Simulation experiments based on the common data samples Penguin and TiltABP verify the effectiveness of the proposed algorithm,and the experiment results show that the results of the MTSC algorithm are completely consistent with that of the Naive algorithm,and the MTSC algorithm can achieve 80%~ 88.3% improvement in time efficiency for the above data samples with an increase in space overhead of 1.1% ~ 9.7%.

Key words: Time series, Content evolution, Time series chain, All-chain set, Incremental calculation

CLC Number: 

  • TP311
[1]LI Z X,LIU H Y.Combining Global and Sequential Patterns for Multivariate Time Series Forecasting [J].Chinese Journal of Computers,2023,46(1):70-84.
[2]PATEL P,KEOGH E,LIN J,et al.Mining Motifs in Massive Time Series Databases[C]//International Conference on Data Mining.IEEE Computer Society,2002:370-377.
[3]MORI U,MENDIBURU A,KEOGH E,et al.Reliable EarlyClassification of Time Series Based on Discriminating the Classes over time[J].Data Mining & Knowledge Discovery,2016,31(1):1-31.
[4]DAU H A,BEGUM N,KEOGH E.Semi-Supervision Dramatically Improves Time Series Clustering under Dynamic Time Warping[C]//International Conference on Information and Know-ledge Management.Association for Computing Machinery,2016:999-1008.
[5]HAO M C,MARWAH M,JANETZKO H,et al.Visual Explo-ration of Frequent Patterns in Multivariate Time Series[J].Information Visualization,2012,11(1):71-83.
[6]SHOKOOHI-YEKTA M,CHEN Y P,CAMPANA B,et al.Dis-covery of Meaningful Rules in Time Series[C]//International Conference on Knowledge Discovery & Data Mining.Association for Computing Machinery,2015:1085-1094.
[7]ZHU Y,IMAMURA M,NIKOVSKI D,et al.Matrix ProfileVII:Time Series Chains:A New Primitive for Time Series Data Mining[C]//International Conference on Data Mining.IEEE,2017:695-704.
[8]HELDT T,OEFINGER M B,HOSHIYAMA M,et al.Circulatory Response to Passive and Active Changes in Posture[C]//Computers in Cardiology.IEEE,2003:263-266.
[9]ZHU Y,IMAMURA M,NIKOVSKI D.et al.Introducing Time Series Chains:A New Primitive for Time Series Data Mining[J].Knowledge and Information Systems,2019,60(2):1135-1161.
[10]TIAN X Z,HU A GU S Y.Research on Stock Market Prediction Method Based on Time Series Chain[J].Journal of Zhejiang University of Technology,2021,49(5):503-510,563.
[11]ZHENG X W,ZOU X N,REN X X,et al.ECG Prediction Based on Bidirectional Time Series Chain Discovery Algorithm[C]//International Conference on Crowd Science and Engineering.Association for Computing Machinery,2021:95-102.
[12]ZHANG L,PATEL N,LI X Q,et al.Joint Time Series Chain:Detecting Unusual Evolving Trend Across Time Series[C]//2022 SIAM International Conference on Data Mining.2022:208-216.
[13]IMAMURA M,NAKAMURA T,KEOGH E.MatrixPro-fileXXI:A Geometric Approach to Time Series Chains Improves Robustness[C]//The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD'20).Association for Computing Machinery,2020:1114-1122.
[14]ZHU Y,ZIMMERMAN Z,SENOBARI N S,et al.Matrix Profile II:Exploiting a Novel Algorithm and GPUs to Break the One Hundred Million Barrier for Time Series Motifs and Joins[C]//IEEE International Conference on Data Mining.IEEE,2016:739-748.
[15]WANG S P,YUAN Y,LI H.Discovering All-Chain Set inStreaming Time Series[C]//The 23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining.Springer Verlag,2019:306-318.
[1] WANG Liqin, WAN Yuan, LUO Ying. Measurable Shapelets Extraction Based on Symbolic Rrepresentation for Time Series Classification [J]. Computer Science, 2024, 51(8): 106-116.
[2] ZENG Zihui, LI Chaoyang, LIAO Qing. Multivariate Time Series Anomaly Detection Algorithm in Missing Value Scenario [J]. Computer Science, 2024, 51(7): 108-115.
[3] SI Jia, LIANG Jianfeng, XIE Shuo, DENG Yingjun. Research Progress of Anomaly Detection in IaaS Cloud Operation Driven by Deep Learning [J]. Computer Science, 2024, 51(6A): 230400016-8.
[4] LUO Ying, WAN Yuan, WANG Liqin. Category-specific and Diverse Shapelets Extraction for Time Series Based on Adversarial Strategies [J]. Computer Science, 2024, 51(5): 35-44.
[5] ZHANG Jianliang, LI Yang, ZHU Qingshan, XUE Hongling, MA Junwei, ZHANG Lixia, BI Sheng. Substation Equipment Malfunction Alarm Algorithm Based on Dual-domain Sparse Transformer [J]. Computer Science, 2024, 51(5): 62-69.
[6] LIN Binwei, YU Zhiyong, HUANG Fangwan, GUO Xianwei. Data Completion and Prediction of Street Parking Spaces Based on Transformer [J]. Computer Science, 2024, 51(4): 165-173.
[7] ZHENG Weinan, YU Zhiyong, HUANG Fangwan. Time Series Completion and One-step Prediction Based on Two-channel Echo State Network [J]. Computer Science, 2024, 51(3): 128-134.
[8] QIAO Fan, WANG Peng, WANG Wei. Multivariate Time Series Classification Algorithm Based on Heterogeneous Feature Fusion [J]. Computer Science, 2024, 51(2): 36-46.
[9] YANG Bo, LUO Jiachen, SONG Yantao, WU Hongtao, PENG Furong. Time Series Clustering Method Based on Contrastive Learning [J]. Computer Science, 2024, 51(2): 63-72.
[10] ZHANG Guohua, YAN Xuefeng, GUAN Donghai. Anomaly Detection of Time-series Based on Multi-modal Feature Fusion [J]. Computer Science, 2023, 50(6A): 220700094-7.
[11] HUANG Fangwan, LU Juhong, YU Zhiyong. Data Augmentation for Cardiopulmonary Exercise Time Series of Young HypertensivePatients Based on Active Barycenter [J]. Computer Science, 2023, 50(6A): 211200233-11.
[12] ZHANG Renbin, ZUO Yicong, ZHOU Zelin, WANG Long, CUI Yuhang. Multimodal Generative Adversarial Networks Based Multivariate Time Series Anomaly Detection [J]. Computer Science, 2023, 50(5): 355-362.
[13] LUO Xiaohui, WU Yun, WANG Chenxing, YU Wenting. Sequential Recommendation Model Based on User’s Long and Short Term Preference [J]. Computer Science, 2023, 50(4): 47-55.
[14] DUAN Mengmeng, JIN Cheng. Transformer Feature Fusion Network for Time Series Classification [J]. Computer Science, 2023, 50(12): 97-103.
[15] WANG Hao, ZHOU Jiantao, HAO Xinyu, WANG Feiyu. Multivariate Time Series Forecasting Method Based on FRA [J]. Computer Science, 2023, 50(11A): 221100144-8.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.