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

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

Аннотация


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

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


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

Полный текст:

PDF

Литература


Zymbler M.L., Kraeva Y.A., Latypova E.A., et al. Cleaning Sensor Data in Intelligent Heating Control System. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 3. P. 16–36. (in Russian) DOI: 10.14529/cmse210302.

Ivanov S.A., Nikolskaya K.Y., Radchenko G.I., et al. Digital Twin of a City: Concept Overview. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2020. Vol. 9, no. 4. P. 5–23. (in Russian) DOI: 10.14529/cmse200401.

Epishev V.V., Isaev A.P., Miniakhmetov R.M., et al. Physiological Data Mining System For Elite Sports. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2013. Vol. 2, no. 1. P. 44–54. (in Russian) DOI: 10.14529/cmse130105.

Abdoulaev S.M., Lenskaia O.U., Gayazova A.O., et al. Short-Range Forecasting Algorithms Using Radar Data: Translation Estimate And Life-Cycle Composite Display. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2014. Vol. 3, no. 1. P. 17–32. (in Russian) DOI: 10.14529/cmse140102.

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 H., Trajcevski G., Scheuermann P., 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.

Zymbler M.L., Poluyanov A.N. Parallel algorithm for imputation of missing values in a streaming time series in real time. Parallel Computational Technologies – 16th International Conference, PCT 2022, Dubna, Russia, March 29-31, 2022. Short papers and posters. Chelyabinsk: SUSU Publishing Center. 2022. P. 128–140. (in Russian) DOI: 10.14529/pct2022.

Khayati M., Lerner A., Tymchenko Z., Cudré-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 É.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 É.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., Böhlen M.H., Dignös 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. P. 10:1–10:31. DOI: 10.1145/2500489.

Kraeva Y.A., Zymbler M.L. The use of MPI and OpenMP technologies for subsequence similarity search in very long time series on a computer cluster system with nodes based on the Intel Xeon Phi Knights Landing many-core processor. Numerical Methods and Programming. 2019. Vol. 20, no. 1. P. 29–44. (in Russian) DOI: 10.26089/NumMet.v20r104.

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. Georgakopoulos, 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. Böhm, 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/JPROC.2018.2853600.

Dau H.A., Keogh E., Kamgar K., et al. The UCR Time Series Classification Archive. 2018. URL: https://www.cs.ucr.edu/~eamonn/time_series_data_2018/ (accessed: 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., Cudré-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/anava15.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. Böhm, 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/JPROC.2018.2847041.

Chlorine Dataset. URL: https://www.cs.cmu.edu/afs/cs/project/spirit-1/www/ (accessed: 03.09.2021).

BundesAmt Für Umwelt – Swiss Federal Office for the Environment. URL: https://www.hydrodaten.admin.ch/en (accessed: 03.09.2021).

Lozano A.C., Li H., 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-Soulié, P.A. Flach, M.J. Zaki. ACM, 2009. P. 587–596. DOI: 10.1145/1557019.1557086.

Laña I., Olabarrieta I., Vélez 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.

Lopukhov I. Real-Time Ethernet network: from theory to practical implementation. MAT: Modern automation technologies. 2010. Vol. 10, no. 3. P. 8–15.

Catalogue 2021. Emerson temperature sensors. URL: https://www.c-o-k.ru/library/catalogs/emerson/110477.pdf (accessed: 03.09.2021).




DOI: http://dx.doi.org/10.14529/cmse220305