research-article

Discord Discovery in Streaming Time Series based on an Improved HOT SAX Algorithm

Authors:

Pham Minh Chau,

Duong Tuan AnhAuthors Info & Claims

SoICT '18: Proceedings of the 9th International Symposium on Information and Communication Technology

Pages 24 - 30

https://doi.org/10.1145/3287921.3287929

Published: 06 December 2018 Publication History

Abstract

In this paper, we propose an improved variant of HOT SAX algorithm, called HS-Squeezer, for efficient discord detection in static time series. HS-Squeezer employs clustering rather than augmented trie to arrange two ordering heuristics in HOT SAX. Furthermore, we introduce HS-Squeezer-Stream, the application of HS-Squeezer in the framework for detecting local discords in streaming time series. The experimental results reveal that HS-Squeezer can detect the same quality discords as those detected by HOT SAX but with much shorter run time. Furthermore, HS-Squeezer-Stream demonstrates a fast response in handling time series streams with quality local discords detected.

References

[1]

Y. Bu, T.W. Leung, A.W.C. Fu, E. Keogh, J. Pei, and S. Meshkin. 2007. WAT: Finding top-k discords in time series database. In Proc. of 2007 SIAM International Conference on Data Mining, Minneapolis, Minnesota, USA, pp. 449--454.

[2]

F. X. Diebold. 2007. Elements of Forecasting, Fourth Edition. Thomson South Western.

Digital Library

[3]

J. Han and M. Kamber. 2011. Data Mining: Concepts and Techniques, 3rd Edition. Morgan Kaufmann Publishing.

Digital Library

[4]

J. A. Hartigan. 1975. Clustering Algorithms, John Wiley & Sons.

Digital Library

[5]

Z. He, X. Xu and S. Deng. 2002. Squeezer: An Efficient Algorithm for Clustering Categorical Data. J. Computer Science and Technology, Vol. 17, No. 5, 611--624.

Digital Library

[6]

E. Keogh, S. Chu, D. Hart, M. Pazzani. 2002. An Online Algorithm for Clustering Categorical Data. J. Computer Science and Technology, Vol. 17, no. 5, 611--624.

Digital Library

[7]

E. Keogh, J. Lin and A. Fu. 2005. HOT SAX: efficiently finding the most unusual time series subsequence. In Proc. of 5th IEE Int. Conf. on Data Mining, (ICDM), Houston, Texas, pp. 226--233.

Digital Library

[8]

E. Keogh, J. Lin, and A. Fu, {online} http://www.cs.ucr.edu/~eamonn/discords/. Accessed in 2017.

[9]

E. Keogh and T. Folias. The UCR Time Series Data Mining Archive. {http://www.cs.ucr.edu/~eamonn/TSDMA/index.html}.

[10]

N.H. Kha, D.T. Anh. 2015. From cluster-based outlier detection to time series discord discovery. Trends and Applications in Knowledge Discovery and Data Mining-PAKDD 2015 Workshops, Ho Chi Minh City, Vietnam, May, X.L. Li et al. (Eds.), LNAI 9441, Springer, 16--28.

Digital Library

[11]

G. Li, O. Braysy, L. Jiang, Z. Wu, Y. Wang. 2013. Finding time series discord based on bit representation clustering. Knowledge-Based Systems, vol.52, pp. 243--254.

[12]

J. Lin, E. Keogh, S. Lonardi, B. Chiu. 2003. Symbolic representation of time series, with implications for streaming algorithms. In Proc. of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, San Diego, CA, June 13.

Digital Library

[13]

Y. Liu, X. Chen, F. Wang, J. Yin. 2009. Efficient Detection of Discords for Time Series Stream. Q. Li et al.(eds), Advances in Data and Web Management, vol. 5446, pp. 629--634.

Digital Library

[14]

H. Sanchez, B. Bustos. 2014. Anomaly Detection in Streaming Time Series Based on Bounding Boxes. In Traina A.J.M., Traina C., Cordeiro R.L.F. (eds) Similarity Search and Applications. SISAP 2014. LNCS 882,. Springer.

[15]

D. Toshniwal and S. Yadav. 2011. 'Adaptive outlier detection in streaming time series. In Proc. of International Conference on Asia Agriculture and Animal. ICAAA 2011, Hong Kong, China, pp. 186--191, 2011

[16]

N. D. K. Vy, D. T. Anh. 2016. Detecting Variable Length Anomaly Patterns in Time Series Data. In Proc. of Int. Conf. on Data Mining and Big Data (DMBD 2016), Bali, Indonesia, June 25-30, Y. Tan, Y. Shi (Eds.), LNCS 9714, Springer, pp. 279--287.

[17]

C.C.M. Yeh, Y. Zhu, L. Ulanova, N. Begum, Y. Ding, H.A. Dau, D.F. Silva, A. Mueen, E. Keogh. 2016. Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View that Includes Motifs, Discords and Shapelets. In 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, Spain, pp. 1317--1322.

Cited By

Sun YCheng DYang TJi YZhang SZhu MXiong XFan QLiang MPei DMa TChen Y(2023)Efficient and Robust KPI Outlier Detection for Large-Scale DatacentersIEEE Transactions on Computers10.1109/TC.2023.327228872:10(2858-2871)Online publication date: Oct-2023
https://doi.org/10.1109/TC.2023.3272288
Bibinbe AMahamadou AMbouopda MNguifo E(2022)DragStream: An Anomaly And Concept Drift Detector In Univariate Data Streams2022 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW58026.2022.00113(842-851)Online publication date: Nov-2022
https://doi.org/10.1109/ICDMW58026.2022.00113
Daigavane AWagstaff KDoran GCochrane CJackman CRymer A(2022)Unsupervised detection of Saturn magnetic field boundary crossings from plasma spectrometer dataComputers & Geosciences10.1016/j.cageo.2022.105040161:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cageo.2022.105040
Show More Cited By

Index Terms

Discord Discovery in Streaming Time Series based on an Improved HOT SAX Algorithm
1. Information systems
  1. Information systems applications
    1. Data mining
      1. Data stream mining

Recommendations

HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence
ICDM '05: Proceedings of the Fifth IEEE International Conference on Data Mining

In this work, we introduce the new problem of finding time series discords. Time series discords are subsequences of a longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the ...
From Cluster-Based Outlier Detection to Time Series Discord Discovery
Revised Selected Papers of the PAKDD 2015 Workshops on Trends and Applications in Knowledge Discovery and Data Mining - Volume 9441

Anomalous patterns or discords are just the kind of outliers in time series. In this paper, we present a new approach for time series discord discovery which is based on cluster-based outlier detection. In this approach, first, subsequence candidates ...
Efficient search for top-k discords in streaming time series

The problem of anomaly detection in streaming time series has received much attention recently. The problem addresses finding the most anomalous subsequence (discord) over a time-series stream, which might arrive at high speed. The fact that finding top-k ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SoICT '18: Proceedings of the 9th International Symposium on Information and Communication Technology

December 2018

496 pages

ISBN:9781450365390

DOI:10.1145/3287921

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SOICT: School of Information and Communication Technology - HUST
NAFOSTED: The National Foundation for Science and Technology Development

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 December 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SoICT 2018

SoICT 2018: The Ninth International Symposium on Information and Communication Technology

December 6 - 7, 2018

Danang City, Viet Nam

Acceptance Rates

Overall Acceptance Rate 147 of 318 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
201
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun YCheng DYang TJi YZhang SZhu MXiong XFan QLiang MPei DMa TChen Y(2023)Efficient and Robust KPI Outlier Detection for Large-Scale DatacentersIEEE Transactions on Computers10.1109/TC.2023.327228872:10(2858-2871)Online publication date: Oct-2023
https://doi.org/10.1109/TC.2023.3272288
Bibinbe AMahamadou AMbouopda MNguifo E(2022)DragStream: An Anomaly And Concept Drift Detector In Univariate Data Streams2022 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW58026.2022.00113(842-851)Online publication date: Nov-2022
https://doi.org/10.1109/ICDMW58026.2022.00113
Daigavane AWagstaff KDoran GCochrane CJackman CRymer A(2022)Unsupervised detection of Saturn magnetic field boundary crossings from plasma spectrometer dataComputers & Geosciences10.1016/j.cageo.2022.105040161:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cageo.2022.105040
Avogadro PDominoni M(2022)A fast algorithm for complex discord searches in time series: HOT SAX TimeApplied Intelligence10.1007/s10489-021-02897-z52:9(10060-10081)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10489-021-02897-z
Meng FGao YWang HLiu YWang H(2021)TSLOD: a coupled generalized subsequence local outlier detection model for multivariate time seriesInternational Journal of Machine Learning and Cybernetics10.1007/s13042-021-01462-x13:5(1493-1504)Online publication date: 15-Nov-2021
https://doi.org/10.1007/s13042-021-01462-x
Son N(2020)An improvement of Disk Aware Discord Discovery Algorithm for Discovering Time Series Discord2020 5th International Conference on Green Technology and Sustainable Development (GTSD)10.1109/GTSD50082.2020.9303111(19-23)Online publication date: 27-Nov-2020
https://doi.org/10.1109/GTSD50082.2020.9303111

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents