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

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

Автор: Цымблер Михаил Леонидович, Полуянов Андрей Николаевич, Краева Яна Александровна

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 3 т.11, 2022 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/147238566

IDR: 147238566   |   DOI: 10.14529/cmse220305

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

  • Цымблер М.Л., Краева Я.А., Латыпова Е.А. и др. Очистка сенсорных данных в интеллектуальных системах управления отоплением зданий / / Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 16-36. DOI: 10.14529/cmse210302.
  • Иванов С.А., Никольская К.Ю., Радченко Г.И. и др. Концепция построения цифрового двойника города // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2020. Т. 9, № 4. С. 5-23. DOI: 10.14529/cmse200401.
  • Епишев В.В., Исаев А.И., Миниахметов Р.М. и др. Система интеллектуального анализа данных физиологических исследований в спорте высших достижений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2013. Т. 2, № 1. С. 44-54. DOI: 10.14529/cmsel30105.
  • Абдуллаев С.М., Ленская О.Ю., Гаязова А.О. и др. Алгоритмы краткосрочного прогноза с использованием радиолокационных данных: оценка трасляции и композиционный дисплей жизненного цикла // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2014. Т. 3, № 1. С. 17-32. DOI: 10.14529/cmsel40102.
  • Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series // Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical Report WS-94-03 / ed. by U.M. Fayyad, R. Uthurusamy. 1994. P. 359-370.
  • Ding Н., Trajcevski G., Scheuermann Р., et al. Querying and mining of time series data: experimental comparison of representations and distance measures // Proc. VLDB Endow. 2008. Vol. 1, no. 2. P. 1542-1552. DOI: 10.14778/1454159.1454226.
  • Цымблер М.Л., Полуянов А.Н. Параллельный алгоритм восстановления пропущенных значений потокового временного ряда в режиме реального времени / / Параллельные вычислительные технологии - XVI международная конференция, ПаВТ’2022, Дубна, 29-31 марта 2022. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ. 2022. С. 128-140. DOI: 10.14529/pct2022.
  • Khayati М., Lerner A., Tymchenko Z., Cudre-Mauroux P. Mind the Gap: An Experimental Evaluation of Imputation of Missing Values Techniques in Time Series // Proc. VLDB Endow. 2020. Vol. 13, no. 5. P. 768-782. DOI: 10.14778/3377369.3377383.
  • Batista G.E.A.P.A., Monard M.C. An Analysis of Four Missing Data Treatment Methods for Supervised Learning // Appl. Artif. Intell. 2003. Vol. 17, no. 5-6. P. 519-533. DOI: 10.1080/713827181.
  • Troyanskaya O.G., Cantor M.N., Sherlock G., et al. Missing value estimation methods for DNA microarrays // Bioinform. 2001. Vol. 17, no. 6. P. 520-525. DOI: 10. 1093/ bioinformatics/17.6.520.
  • Hsu H., Yang A.C., Lu M. KNN-DTW Based Missing Value Imputation for Microarray Time Series Data // J. Comput. 2011. Vol. 6, no. 3. P. 418-425. DOI: 10.4304/jcp.6.3.418-425.
  • Phan T., Poisson E.C., Bigand A., Lefebvre A. DTW-Approach for uncorrelated multivariate time series imputation // 27th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2017, Tokyo, Japan, September 25-28, 2017 / ed. by N. Ueda, S. Watanabe, T. Matsui, et al. 2017. P. 1-6. DOI: 10.1109/MLSP. 2017.8168165.
  • Phan T., Caillault E.P., Lefebvre A., Bigand A. Dynamic time warping-based imputation for univariate time series data // Pattern Recognit. Lett. 2020. Vol. 139. P. 139-147. DOI: 10.1016/j.patrec.2017.08.019.
  • Keogh E.J., Pazzani M.J. Derivative Dynamic Time Warping // Proceedings of the 1st SIAM International Conference on Data Mining, SDM 2001, Chicago, IL, USA, April 5-7, 2001 / ed. by V. Kumar, R.L. Grossman. 2001. P. 1-11. DOI: 10.1137/1.9781611972719.1.
  • Wellenzohn K., Bohlen M.H., Dignos A., et al. Continuous Imputation of Missing Values in Streams of Pattern-Determining Time Series / / Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017 / ed. by V. Markl, S. Orlando, B. Mitschang, et al. 2017. P. 330-341. DOI: 10.5441/ 002/edbt.2017.30.
  • Rakthanmanon T., Campana B.J.L., Mueen A., et al. Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping // ACM Trans. Knowl. Discov. Data. 2013. Vol. 7, no. 3. 10:1-10:31. DOI: 10.1145/2500489.
  • Краева Я.А., Цымблер М.Л. Совместное использование технологий MPI и ОрепМР для параллельного поиска похожих подпоследовательностей в сверхбольших временных рядах на вычислительном кластере с узлами на базе многоядерных процессоров Intel Xeon Phi Knights Landing // Вычислительные методы и программирование. 2019. Т. 20, № 1. С. 29-44. DOI: 10.26089/NumMet. v20rl04.
  • Kim S., Park S., Chu W.W. An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases / / Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany / ed. by D. Geor-gakopoulos, A. Buchmann. 2001. P. 607-614. DOI: 10.1109/ICDE.2001.914875.
  • Fu A.W., Keogh E.J., Lau L.Y.H., Ratanamahatana C. Scaling and Time Warping in Time Series Querying // Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005 / ed. by K. Bohm, C.S. Jensen, L.M. Haas, et al. 2005. P. 649-660. URL: http://www.vldb.org/archives/website/ 2005/program/paper/thu/p649-fu.pdf.
  • Supinski B.R. de, Scogland T.R.W., Duran A., et al. The Ongoing Evolution of OpenMP // Proc. IEEE. 2018. Vol. 106, no. 11. P. 2004-2019. DOI: 10.1109/JPR0C.2018.2853600.
  • Dau H.A., Keogh E., Kamgar К. и др. The UCR Time Series Classification Archive. 2018. URL: https : //www. cs . ucr. edu/~eamonn/time_series_data_2018/ (дата обращения: 12.04.2022).
  • Mueen A., Keogh E.J., Zhu Q., et al. Exact Discovery of Time Series Motifs // Proceedings of the SIAM International Conference on Data Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada, USA. SIAM, 2009. P. 473-484. DOI: 10.1137/1.9781611972795.41.
  • Dolganina N., Ivanova E., Bilenko R., Rekachinsky A. HPC resources of South Ural State University // 16th International Conference on Parallel Computational Technologies, PCT 2022, Dubna, Russia, March 29-31, 2022, Revised Selected Papers. Communications in Computer and Information Science. Vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. Springer, 2022. P. 43-55. DOI: 10.1007/978-3-031-11623-0_4.
  • Khayati M., Arous I., Tymchenko Z., Cudre-Mauroux P. ORBITS: Online Recovery of Missing Values in Multiple Time Series Streams // Proc. VLDB Endow. 2020. Vol. 14, no. 3. P. 294-306. DOI: 10.5555/3430915.3442429.
  • Anava O., Hazan E., Zeevi A. Online Time Series Prediction with Missing Data // Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, July 6-11, 2015. 2015. P. 2191-2199. URL: http://proceedings .mlr .press/v37/ anaval5.html.
  • Papadimitriou S., Sun J., Faloutsos C. Streaming Pattern Discovery in Multiple Time-Series // Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005 / ed. by K. Bohm, C.S. Jensen, L.M. Haas, et al. 2005. P. 697-708. DOI: 10.5555/1083592.1083674.
  • Balzano L., Chi Y., Lu Y.M. Streaming PCA and Subspace Tracking: The Missing Data Case // Proc. IEEE. 2018. Vol. 106, no. 8. P. 1293-1310. DOI: 10. 1109/JPR0C . 2018 . 2847041.
  • Chlorine Dataset. URL: https://www.cs.cmu.edu/afs/cs/project/spirit-l/www/ (дата обращения: 03.09.2021).
  • BundesAmt Fur Umwelt - Swiss Federal Office for the Environment. URL: https://www. hydrodaten. admin, ch/en (дата обращения: 03.09.2021).
  • Lozano А.С., Li LL, Niculescu-Mizil A., et al. Spatial-temporal causal modeling for climate change attribution // Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28 - July 1, 2009 / ed. by J.F. Elder IV, F. Fogelman-Soulie, P.A. Flach, M.J. Zaki. ACM, 2009. P. 587-596. DOI: 10.1145/1557019.1557086.
  • Lana I., Olabarrieta I., Velez M., Del Ser J. On the imputation of missing data for road traffic forecasting: New insights and novel techniques // Transportation Research Part C: Emerging Technologies. 2018. Vol. 90. P. 18-33. DOI: 10.1016/j .trc.2018.02.021.
  • Lefebvre A. MAREL Carnot data and metadata from Coriolis Data Centre. SEANOE. 2015. DOI: 10.17882/39754.
  • Лопухов И. Сети Real-Time Ethernet: от теории к практической реализации // СТА: Современные технологии автоматизациии. 2010. Т. 10, № 3. С. 8-15.
  • Каталог 2021. Датчики температуры Emerson. URL: https://www.c-o-k.ru/library/ catalogs/emerson/110477.pdf (дата обращения: 03.09.2021).
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp