Реферат: В настоящее время во многих предметных областях обработка потоковых временных рядов в режиме реального времени связана с необходимостью синтеза значения ряда, которое было пропущено ввиду технического сбоя или человеческого фактора. В данной статье предлагается параллельный алгоритм восстановления пропущенных значений потокового временного ряда в режиме реального времени для многоядерного процессора. Алгоритм использует набор опорных временных рядов (reference time series), которые имеют семантическую связь с исходным рядом и упорядочены по убыванию корреляции с ним. Алгоритм применяет следующую эвристику: если в опорных рядах имеют место повторяющиеся (схожие) подпоследовательности, то в ряде, содержащем пропущенное значение, повторяющиеся подпоследовательности возникают в тех же временн´ых интервалах. Образцами поиска для каждого опорного ряда полагаются подпоследовательности заданной длины, оканчивающиеся в момент пропуска значения в исходном ряде. Схожесть подпоследовательностей с образцом определяется на основе меры DTW (Dynamic Time Warping), имеющей квадратичную вычислительную сложность относительно длины подпоследовательности. Применяется техника нижних границ (lower bounding), позволяющая отбрасывать подпоследовательности, заведомо непохожие на образец поиска, без вычисления DTW. Нижние границы схожести имеют меньшую чем квадратичную сложность и вычисляются параллельно с помощью технологии программирования OpenMP. Восстановленное значение вычисляется как среднее арифметическое последних элементов найденных интервалов. В вычислительных экспериментах предложенный алгоритм демонстрирует приемлемое качество и высокое быстродействие восстановления, что позволяет применять алгоритм в режиме реального времени.

Библиографическая ссылка: Полуянов А.Н. , Цымблер М.Л.
Параллельный алгоритм восстановления пропущенных значений потокового временного ряда в режиме реального времени
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ ПАВТ-2022 29-31 мар. 2022