Сотрудники Южно-Уральского государственного университета Михаил Цымблер и Яна Краева создали параллельный алгоритм PADDi для поиска аномалий в огромных временных рядах.
Такие ряды возникают там, где датчики снимают показания тысячи раз в секунду: в медицине, на производстве, в интернете вещей, сейсморазведке и электронной торговле. Миллионы точек невозможно проанализировать вручную, а традиционные алгоритмы либо медленны, либо требуют дорогой экспертизы.
PADDi использует понятие «диссонанс» — участок ряда, который резко отличается от остальных. Алгоритму не нужны глубокие знания в предметной области: достаточно знать лишь длину искомой аномалии. Обработка идет на двух уровнях. Сначала данные делятся на фрагменты, каждый обрабатывает отдельный узел кластера. Затем фрагмент разбивается на сегменты, и каждый сегмент обрабатывает графический процессор (GPU). Узлы и GPU обмениваются результатами — это ключевое ноу‑хау. Если бы каждый узел искал аномалии только в своем куске, локальные выбросы могли бы ошибочно принять за глобальные. Обмен информацией решает эту проблему.
Обработка большого временного ряда организуется на двух уровнях. Сначала данные разделяются на фрагменты, каждый из которых обрабатывается отдельным узлом кластера. Затем фрагмент разделяется на сегменты, и каждый сегмент обрабатывается графическими процессорами кластерного узла. На каждом из уровней узлы и GPU обмениваются полученными результатами. Если просто найти аномалии в отдельном фрагменте или сегменте, а затем предъявить все найденное как ответ, то это не сработает, ведь аномалия для какой-то части данных может не быть аномалией для всего объема
Алгоритм проверили на суперкомпьютерах «Ломоносов‑2» и «Лобачевский» с рядами из миллионов точек. PADDi оказался быстрее лучших аналогов, а его скорость растет почти линейно с добавлением графических процессоров — это редкое свойство для параллельных программ. Такой результат достигнут благодаря тому, что узлы кластера обмениваются данными как можно реже. На сегодня PADDi — единственный алгоритм, который умеет эффективно искать аномалии в огромных временных рядах на кластерах с множеством GPU. Исследование опубликовано в Lobachevskii Journal of Mathematics.
Ранее Наука Mail писала о том, что новгородские инженеры разработали магнитокардиометр для диагностики сердца.
