Cited By
View all- Kraeva YZymbler M(2023)A Parallel Discord Discovery Algorithm for a Graphics ProcessorPattern Recognition and Image Analysis10.1134/S105466182302006233:2(101-112)Online publication date: 1-Jun-2023
A new discord definition and an efficient time series discord detection method using GPUs
Pages 63 - 70
Abstract
Discord is the most unusual subsequence in a time series. Most of the methods for discord detection in time series belong to the window-based category which uses a sliding window with a pre-specified length. Besides, a discord may appear twice or more times so that any instance of this discord does not qualify to be an abnormal. In addition, computational cost of window-based methods for discord detection is still high. In this paper, we propose a GPU-based parallel method, called KBF_GPU, for time series discord detection with a new definition of discord and no requirement for a pre-specified discord length. With the new discord definition, KBF_GPU can detect exactly the discord in case of there are more than one similar discords in time series. By using GPU programming techniques to parallelize Brute-Force algorithm with the new discord definition, our proposed KBF_GPU can run about 10,216 times faster than Brute-Force algorithm with the new discord definition on average over seven benchmark datasets.
References
[1]
Keogh, Eamonn, Jessica Lin, and Ada Fu. 2005. HOT SAX: Efficiently finding the most unusual time series subsequence. In Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM'05), 226-233. https://doi.org/10.1109/icdm.2005.79
[2]
Keogh, Eamonn, Kaushik Chakrabarti, Michael Pazzani, and Sharad Mehrotra. 2001. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems, 3, 3, 263-286. https://doi.org/10.1007/pl00011669
[3]
Lin, Jessica, Eamonn Keogh, Stefano Lonardi, and Bill Chiu. 2003. Symbolic representation of time series, with implications for streaming algorithms. In Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, San Diego, CA. https://doi.org/10.1145/882082.882086
[4]
Bu, Yingyi, Tat-Wing Leung, Ada Wai-Chee Fu, Eamonn Keogh, Jian Pei, and Sam Meshkin. 2007. WAT: Finding top-k discords in time series database. In Proceedings of the 2007 SIAM International Conference on Data Mining, 449-454. https://doi.org/10.1137/1.9781611972771.43
[5]
Salvador, Stan, and Philip Chan. 2005. Learning states and rules for time series anomaly detection. Applied Intelligence, 23, 3, 241-255. https://doi.org/10.1007/s10489-005-4610-3
[6]
Buu, Huynh Tran Quoc, and Duong Tuan Anh. 2011. Time series discord discovery based on iSAX symbolic representation. In Proceedings of the 2011 Third International Conference on Knowledge and Systems Engineering (KSE), Hanoi, Vietnam, 11-18. https://doi.org/10.1109/kse.2011.11
[7]
Li, Guiling, Olli Bräysy, Liangxiao Jiang, Zongda Wu, and Yuanzhen Wang. 2013. Finding time series discord based on bit representation clustering. Knowledge-Based Systems, 54, 243-254. https://doi.org/10.1016/j.knosys.2013.09.015
[8]
Kha, Nguyen Huy, and Duong Tuan Anh. 2015. From Cluster-Based Outlier Detection to Time Series Discord Discovery. Trends and Applications in Knowledge Discovery and Data Mining. Springer, PAKDD 2015 Workshops: Big_PMA, VLSP, QIMIE, BAEBH, Ho Chi Minh City, Vietnam, 16-28. https://doi.org/10.1007/978-3-319-25660-3_2
[9]
Chandola, Varun, Arindam Banerjee, and Vipin Kumar. 2009. Anomaly detection: a survey. ACM computing surveys (CSUR), 41, 3, 1-58. https://doi.org/10.1145/1541880.1541882
[10]
Huang, Tian, Yongxin Zhu, Yafei Wu, and Weiwei Shi. 2015. J-distance discord: an improved time series discord definition and discovery method. In Proceedings of 15th Internatioal Conference on Data Mining Workshops, 303-310. https://doi.org/10.1109/icdmw.2015.120
[11]
Zhang, Li, Yifeng Gao, and Jessica Lin. 2020. Semantic Discord: Finding unusual local patterns for time series. In Proceedings of 2020 SIAM International Conference on Data Mining (SDM).
[12]
Wei, Li, Eamonn Keogh, and Xiaopeng Xi. 2006. Saxually explicit images: Finding unusual shapes. In Proceedings of ICDM, 711-720. https://doi.org/10.1109/icdm.2006.138
[13]
Sart, Doruk, Abdullah Mueen, Walid Najjar, Eamonn Keogh, and Vit Niennattrakul. 2010. Accelerating Dynamic Time Warping Subsequence Search with GPUs and FPGAs. In Proceedings of the In-ternational Conference on Data Mining, 1001-1006. https://doi.org/10.1109/icdm.2010.21
[14]
Chang, Kai-Wei, Biplab Deka, Wen-Mei W. Hwu, and Dan Roth. 2012. Efficient Pattern-based Time Series Classification on GPU. In Proceedings of the IEEE 12th International Conference on Data Mining, 131-140. https://doi.org/10.1109/icdm.2012.132
[15]
Zhu, Yan, Zachary Zimmerman, Nader Shakibay Senobari, Chin-Chia Michael Yeh, Gareth Funning, Abdullah Mueen, Philip Brisk, and Eamonn Keogh. 2016. Matrix Profile II: Exploiting a novel algorithm and GPUs to break the one hundred million barrier for time series motifs and joins. In Proceedings of the IEEE 16th International Conference on Data Mining, 739-748. https://doi.org/10.1109/icdm.2016.0085
[16]
Zhu, Biru, Youyou Jiang, Ming Gu, and Yangdong Deng. 2021. A GPU acceleration framework for motif and discord based pattern mining. IEEE Transactions on Parallel and Distributed Systems, 32, 8, 1987-2004. https://doi.org/10.1109/tpds.2021.3055765
[17]
NVIDIA. 2017. CUDA Programming Guide Version 8.0, https://docs.nvidia.com/cuda/index.html
[18]
NVIDIA. 2017. CUDA Toolkit Documentation Version 8.0, https://docs.nvidia.com/cuda/index.html
[19]
Thuy, Huynh Thi Thu, Duong Tuan Anh, and Vo Thi Ngoc Chau. 2016. Some segmentation-based techniques to improve time series discord discovery. In Proceedings of the International Conference on Nature of Computation and Communication (ICCTC 2016). Springer, Rach Gia, Vietnam, 179-188. https://doi.org/10.1007/978-3-319-46909-6_17
[20]
Fink, Eugene, and Harith Suman Gandhi. 2007. Important extrema of time series. In Proceedings of the IEEE International Conference on System, Man and Cybernetics. Montreal, Canada, 366-372. https://doi.org/10.1109/icsmc.2007.4414161
[21]
Lin, Jessica, Eamonn Keogh, P. Patel, and Stefano Lonardi. 2002. Finding motifs in time series. In Proceedings of the 2nd Workshop on Temporal Data Mining, The 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (KDD 2002), 23-26.
[22]
Keogh, Eamonn. 2020. The website of UCR Archive, https://www.cs.ucr.edu/∼eamonn/discords
[23]
Dau, H. A., Keogh, E., Kamgar, K., Yeh, C. M., Zhu, Y., Gharghabi, S., Ratanamahatana, C. A., Chen, Y., Hu, B., Begum, N., Bagnall, A. Mueen, A., Batista, G., Hexagon-ML. 2020. The UCR Time Series Classification Archive, https://www.cs.ucr.edu/∼eamonn/time_series_data_2018/
Index Terms
- A new discord definition and an efficient time series discord detection method using GPUs
Index terms have been assigned to the content through auto-classification.
Recommendations
Can quantum discord increase in a quantum communication task?
Quantum teleportation of an unknown quantum state is one of the few communication tasks which has no classical counterpart. Usually the aim of teleportation is to send an unknown quantum state to a receiver. But is it possible in some way that the ...
Geometric measure of quantum discord under decoherence
The dynamics of a geometric measure of the quantum discord (GMQD) under decoher-ence is investigated. We show that the GMQD of a two-qubit state can be alternativelyobtained through the singular values of a 3times;4 matrix whose elements are the ...
General bounds for quantum discord and discord distance
For any bipartite state, how strongly can one subsystem be quantum correlated with another? Using the Koashi---Winter relation, we study the upper bound of purified quantum discord, which is given by the sum of the von Neumann entropy of the unmeasured ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2021
75 pages
ISBN:9781450385213
DOI:10.1145/3507473
Copyright © 2021 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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 February 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICSED 2021
ICSED 2021: 2021 3rd International Conference on Software Engineering and Development
November 19 - 21, 2021
Xiamen, China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 62Total Downloads
- Downloads (Last 12 months)14
- Downloads (Last 6 weeks)1
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
Cited By
View all- Kraeva YZymbler M(2023)A Parallel Discord Discovery Algorithm for a Graphics ProcessorPattern Recognition and Image Analysis10.1134/S105466182302006233:2(101-112)Online publication date: 1-Jun-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format