DOI: https://doi.org/10.26089/NumMet.v24r321

Поиск аномалий в больших временных рядах на кластере с GPU узлами

Авторы

  • Я. А. Краева
  • М. Л. Цымблер

Ключевые слова:

временной ряд
поиск аномалий
диссонанс
параллельный алгоритм
вычислительный кластер
графический процессор
CUDA
DRAG
MERLIN
PD3
PALMAD

Аннотация

В настоящее время обнаружение аномалий в длинных временных рядах возникает в широком спектре предметных областей: цифровая индустрия, здравоохранение, моделирование климата, финансовая аналитика и др.  Диссонанс формализует понятие аномалии и определяется как подпоследовательность ряда, которая имеет расстояние до своего ближайшего соседа, не превышающее наперед заданного аналитиком порога. Ближайшим соседом подпоследовательности является та подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее. В статье представлен новый алгоритм поиска диссонансов временн´ого ряда на вычислительном кластере, каждый узел которого оснащен графическим процессором. Алгоритм применяет параллелизм по данным: временн´ой ряд разбивается на непересекающиеся фрагменты, обрабатываемые графическими процессорами узлов вычислительного кластера. С помощью ранее разработанного авторами параллельного алгоритма на каждом узле выполняется отбор локальных кандидатов в диссонансы. Далее с помощью обменов на каждом узле формируется множество глобальных кандидатов как объединение всех локальных кандидатов. Затем каждый узел выполняет глобальную очистку, удаляя из множества глобальных кандидатов ложноположительные диссонансы. Глобальная очистка распараллеливается на основе блочного умножения матрицы кандидатов и матрицы подпоследовательностей фрагмента. Результирующее множество диссонансов формируется как пересечение множеств, полученных узлами по итогу глобальной очистки. Вычислительные эксперименты с синтетическими и реальными временными рядами, проведенные на платформе суперкомпьютеров Ломоносов-2 и Лобачевский, оснащенных 48–64 графическими процессорами, показывают высокую масштабируемость разработанного алгоритма.

Загрузки

Опубликован

2023-08-31

Выпуск

Том 24 (2023): Выпуск 3.

Раздел

Параллельные программные средства и технологии

Авторы

Я. А. Краева

Южно-Уральский государственный университет (национальный исследовательский университет),
Научно-образовательный центр “Искусственный интеллект и квантовые технологии”,
просп. им. В.И. Ленина, д. 76, 454080, Челябинск
• начальник отдела

М. Л. Цымблер

Южно-Уральский государственный университет (национальный исследовательский университет),
Научно-образовательный центр “Искусственный интеллект и квантовые технологии”,
просп. им. В.И. Ленина, д. 76, 454080, Челябинск
• доцент, заместитель директора центра

Библиографические ссылки

  1. A. Blázquez-Garcıa, A. Conde, U. Mori, and J. A. Lozano, “A Review on Outlier/Anomaly Detection in Time Series Data,” ACM Comput. Surv. 54 (3), 56: 1-56: 33 (2021).
    doi 10.1145/3444690
  2. V. Chandola, A. Banerjee, and V. Kumar, “Anomaly Detection: A Survey,” ACM Comput. Surv. 41 (3), 15: 1-15: 58 (2009).
    doi 10.1145/1541880.1541882
  3. V. Chandola, D. Cheboli, and V. Kumar, Detecting Anomalies in a Time Series Database , Technical Report TR 09-004 (University of Minnesota, Minneapolis, 2009).
    https://hdl.handle.net/11299/215791 . Cited August 23, 2023.
  4. J. Lin, E. Keogh, A. Fu, and H. V. Herle, “Approximations to Magic: Finding Unusual Medical Time Series,” in Proc. 18th IEEE Symposium on Computer-Based Medical Systems (CBMS 2005), Dublin, Ireland, June 23-24, 2005 (IEEE Press, Washington D.C., 2005), pp. 329-334.
    doi 10.1109/CBMS.2005.34
  5. A. L. Goldberger, L. A. N. Amaral, L. Glass, et al., “PhysioBank, PhysioToolkit, and PhysioNet Components of a New Research Resource for Complex Physiologic Signals,” Circulation 101 (23), e215-e220 (2000).
    doi 10.1161/01.CIR.101.23.e215.
  6. T. Nakamura, M. Imamura, R. Mercer, and E. Keogh, “MERLIN: Parameter-Free Discovery of Arbitrary Length Anomalies in Massive Time Series Archives,” in Proc. 20th IEEE Int. Conf. on Data Mining (ICDM 2020), Sorrento, Italy, November 17-20, 2020 (IEEE Press, New York, 2020), pp. 1190-1195.
    doi 10.1109/ICDM50108.2020.00147
  7. M. Zymbler and Y. Kraeva, “High-Performance Time Series Anomaly Discovery on Graphics Processors,” Mathematics 11 (14), Article Number 3193 (2023).
    doi 10.3390/math11143193
  8. J. Lin, E. Keogh, S. Lonardi, and B. Chiu, “A 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 (DMKD 2003), San Diego, California, USA, June 13, 2003 (ACM Press, New York, 2003), pp. 2-11.
    doi 10.1145/882082.882086
  9. M. L. Zymbler, “A Parallel Discord Discovery Algorithm for Time Series on Many-Core Accelerators,” Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie) 20 (3), 211-223 (2019).
    doi 10.26089/NumMet.v20r320
  10. D. Yankov, E. Keogh, and U. Rebbapragada, “Disk Aware Discord Discovery: Finding Unusual Time Series in Terabyte Sized Datasets,” in Proc. of the 7th IEEE Int. Conf. on Data Mining (ICDM 2007), Omaha, Nebraska, USA, October 28-31, 2007 (IEEE Press, New York, 2007), pp. 381-390.
    doi 10.1109/ICDM.2007.61
  11. D. Yankov, E. Keogh, and U. Rebbapragada, “Disk Aware Discord Discovery: Finding Unusual Time Series in Terabyte Sized Datasets,” Knowl. Inf. Syst. 17 (2), 241-262 (2008).
    doi 10.1007/s10115-008-0131-9
  12. Ya. A. Kraeva and M. L. Zymbler, “A Parallel Discord Discovery Algorithm for a Graphics Processor,” Pattern Recognit. Image Anal. 33 (2), 101-112 (2023).
    doi 10.1134/S1054661823020062
  13. M. Zymbler, A. Grents, Y. Kraeva, and S. Kumar, “A Parallel Approach to Discords Discovery in Massive Time Series Data,” Comput. Mater. Contin. 66 (2), 1867-1878, 2021.
    doi 10.32604/cmc.2020.014232
  14. Y. Wu, Y. Zhu, T. Huang, et al., “Distributed Discord Discovery: Spark Based Anomaly Detection in Time Series,” in 17th IEEE Int. Conf. on High Performance Computing and Communications (HPCC 2015), 7th IEEE Int. Symposium on Cyberspace Safety and Security (CSS 2015), and 12th IEEE Int. Conf. on Embedded Software and Systems (ICESS 2015), New York, USA, August 24-26, 2015 (IEEE Press, New York, 2015), pp. 154-159.
    doi 10.1109/HPCC-CSS-ICESS.2015.228
  15. T. Huang, Y. Zhu, Y. Mao, et al., “Parallel Discord Discovery,” in Lecture Notes in Computer Science (Springer, Cham, 2016), Vol. 9652, pp. 233-244.
    doi 10.1007/978-3-319-31750-2_19
  16. A. Mueen, S. Nath, and J. Liu, “Fast Approximate Correlation for Massive Time-Series Data,” in Proc. of the ACM SIGMOD Int. Conf. on Management of Data (SIGMOD 2010), Indianapolis, Indiana, USA, June 6-10, 2010 (ACM Press, New York, 2010), pp. 171-182.
    doi 10.1145/1807167.1807188
  17. Individual Household Electric Power Consumption.
    https://archive.ics.uci.edu/ml/datasets/individual+household+electric+power+consumption/. Cited August 24, 2023.
  18. M. Thill, W. Konen, and T. Bäck, “MarkusThill/MGAB: The Mackey-Glass Anomaly Benchmark. Version v1.0.1,” Zenodo, 2020.
    doi 10.5281/ZENODO.3762385
  19. M. C. Mackey and L. Glass, “Oscillation and Chaos in Physiological Control Systems,” Science 197 (4300), 287-289 (1977).
    doi 10.1126/science.267326
  20. Vl. V. Voevodin, A. S. Antonov, D. A. Nikitenko, et al., “Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community,” Supercomput. Front. Innov. 6 (2), 4-11 (2019).
    doi 10.14529/jsfi190201
  21. Z. Zimmerman, K. Kamgar, N. S. Senobari, et al., “Matrix Profile XIV: Scaling Time Series Motif Discovery with GPUs to Break a Quintillion Pairwise Comparisons a Day and Beyond,” in Proc. of the ACM Symposium on Cloud Computing (SoCC 2019), Santa Cruz, CA, USA, November 20-23, 2019. (ACM Press, New York, 2019), pp. 74-86.
    doi 10.1145/3357223.3362721
  22. C.-C. M. Yeh, Y. Zhu, L. Ulanova, et al., “Time Series Joins, Motifs, Discords and Shapelets: A Unifying View that Exploits the Matrix Profile,” Data Min. Knowl. Discov. 32 (1), 83-123 (2018).
    doi 10.1007/s10618-017-0519-9

Лицензия

Copyright (c) 2023 Я. А. Краева, М. Л. Цымблер

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.