Параллельный алгоритм восстановления сенсорных данных в режиме реального времени для многоядерного процессора | Sciact - Система учета научной деятельности ИМ СО РАН

Параллельный алгоритм восстановления сенсорных данных в режиме реального времени для многоядерного процессора Научная публикация

Журнал

Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
ISSN: 2305-9052 , E-ISSN: 2410-7034

Вых. Данные

Год: 2022, Том: 11, Номер: 3, Страницы: 69-90 Страниц : 22 DOI: 10.14529/cmse220305

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

временной ряд; восстановление пропущенных значений; параллельный алгоритм; многоядерный процессор; DTW; отбрасывание по нижним границам

Авторы

Цымблер М.Л. ¹ , Полуянов А.Н. ² , Краева Я.А. ¹

Организации

1	Южно-Уральскийгосударственныйуниверситет (454080,Челябинск,пр.им.В.И.Ленина,д.76)
2	Институт математики им.С.Л.Соболева СО РАН (644043,Омск,ул.Певцова,д.13)

Информация о финансировании (3)

1	Российский фонд фундаментальных исследований	20-07-00140
2	Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».	FWNF-2022-0016
3	Министерство науки и высшего образования РФ	FENU-2020-0022

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

Цымблер М.Л. , Полуянов А.Н. , Краева Я.А.
Параллельный алгоритм восстановления сенсорных данных в режиме реального времени для многоядерного процессора
Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2022. Т.11. №3. С.69-90. DOI: 10.14529/cmse220305 РИНЦ OpenAlex

Поступила в редакцию:	30 июл. 2022 г.
Опубликована в печати:	7 окт. 2022 г.
Опубликована online:	7 окт. 2022 г.

РИНЦ:	49502700
OpenAlex:	W4312635386

Пока нет цитирований