{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T13:05:55Z","timestamp":1793711155077,"version":"4.6.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>Sensor data streams occur widely in various real-time applications in the context of the Internet of Things (IoT). However, sensor data streams feature missing values due to factors such as sensor failures, communication errors, or depleted batteries. Missing values can compromise the quality of real-time analytics tasks and downstream applications. Existing imputation methods either make strong assumptions about streams or have low efficiency. In this study, we aim to accurately and efficiently impute missing values in data streams that satisfy only general characteristics in order to benefit real-time applications more widely. First, we propose a message propagation imputation network (MPIN) that is able to recover the missing values of data instances in a time window. We give a theoretical analysis of why MPIN is effective. Second, we present a continuous imputation framework that consists of data update and model update mechanisms to enable MPIN to perform continuous imputation both effectively and efficiently. Extensive experiments on multiple real datasets show that MPIN can outperform the existing data imputers by wide margins and that the continuous imputation framework is efficient and accurate.<\/jats:p>","DOI":"10.14778\/3632093.3632100","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T06:26:31Z","timestamp":1705731991000},"page":"345-358","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Missing Value Imputation for Multi-Attribute Sensor Data Streams via Message Propagation"],"prefix":"10.14778","volume":"17","author":[{"given":"Xiao","family":"Li","sequence":"first","affiliation":[{"name":"Roskilde University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huan","family":"Li","sequence":"additional","affiliation":[{"name":"Zhejiang University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hua","family":"Lu","sequence":"additional","affiliation":[{"name":"Roskilde University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Varun","family":"Pandey","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Markl","sequence":"additional","affiliation":[{"name":"TU Berlin, BIFOLD, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. Extended Version. https:\/\/arxiv.org\/pdf\/2311.07344.pdf."},{"key":"e_1_2_1_2_1","unstructured":"2023. MPIN project: code and datasets. https:\/\/github.com\/XLI-2020\/MPIN."},{"key":"e_1_2_1_3_1","unstructured":"2023. SimpleImputer. https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.impute.SimpleImputer.html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_2_1_5_1","volume-title":"RecovDB: Accurate and Efficient Missing Blocks Recovery for Large Time Series. In 35th IEEE International Conference on Data Engineering, ICDE 2019","author":"Arous Ines","year":"2019","unstructured":"Ines Arous, Mourad Khayati, Philippe Cudr\u00e9-Mauroux, Ying Zhang, Martin L. Kersten, and Svetlin Stalinlov. 2019. RecovDB: Accurate and Efficient Missing Blocks Recovery for Large Time Series. In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8--11, 2019. IEEE, 1976--1979."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/mpr.329"},{"key":"e_1_2_1_7_1","unstructured":"Peter W. Battaglia Jessica B. Hamrick Victor Bapst Alvaro Sanchez-Gonzalez Vin\u00edcius Flores Zambaldi Mateusz Malinowski Andrea Tacchetti David Raposo Adam Santoro Ryan Faulkner \u00c7aglar G\u00fcl\u00e7ehre H. Francis Song Andrew J. Ballard Justin Gilmer George E. Dahl Ashish Vaswani Kelsey R. Allen Charles Nash Victoria Langston Chris Dyer Nicolas Heess Daan Wierstra Pushmeet Kohli Matthew M. Botvinick Oriol Vinyals Yujia Li and Razvan Pascanu. 2018. Relational inductive biases deep learning and graph networks. CoRR abs\/1806.01261 (2018). arXiv:1806.01261 http:\/\/arxiv.org\/abs\/1806.01261"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204032"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137641"},{"key":"e_1_2_1_10_1","volume-title":"BRITS: Bidirectional Recurrent Imputation for Time Series. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Cao Wei","year":"2018","unstructured":"Wei Cao, Dong Wang, Jian Li, Hao Zhou, Lei Li, and Yitan Li. 2018. BRITS: Bidirectional Recurrent Imputation for Time Series. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montr\u00e9al, Canada. 6776--6786."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-018-24271-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2208.06573"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50036-6"},{"key":"e_1_2_1_14_1","volume-title":"Multivariate Time Series Imputation by Graph Neural Networks. CoRR abs\/2108.00298","author":"Cini Andrea","year":"2021","unstructured":"Andrea Cini, Ivan Marisca, and Cesare Alippi. 2021. Multivariate Time Series Imputation by Graph Neural Networks. CoRR abs\/2108.00298 (2021). arXiv:2108.00298"},{"key":"e_1_2_1_15_1","volume-title":"International Conference on Learning Representations.","author":"Cini Andrea","year":"2022","unstructured":"Andrea Cini, Ivan Marisca, and Cesare Alippi. 2022. Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2023.119619"},{"key":"e_1_2_1_17_1","volume-title":"Incremental Training of Graph Neural Networks on Temporal Graphs under Distribution Shift. CoRR abs\/2006.14422","author":"Galke Lukas","year":"2020","unstructured":"Lukas Galke, Iacopo Vagliano, and Ansgar Scherp. 2020. Incremental Training of Graph Neural Networks on Temporal Graphs under Distribution Shift. CoRR abs\/2006.14422 (2020). arXiv:2006.14422 https:\/\/arxiv.org\/abs\/2006.14422"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Gilmer Justin","year":"2017","unstructured":"Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6--11 August 2017 (Proceedings of Machine Learning Research), Vol. 70. PMLR, 1263--1272."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Eleventh International Conference on Management of Data, January 6, 7, and 8","author":"Halatchev Mihail","year":"2005","unstructured":"Mihail Halatchev and Le Gruenwald. 2005. Estimating Missing Values in Related Sensor Data Streams. In Advances in Data Management 2005, Proceedings of the Eleventh International Conference on Management of Data, January 6, 7, and 8, 2005, Goa, India, Jayant R. Haritsa and T. M. Vijayaraman (Eds.). Computer Society of India, 83--94."},{"key":"e_1_2_1_20_1","volume-title":"Inductive representation learning on large graphs. Advances in neural information processing systems 30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7"},{"key":"e_1_2_1_22_1","volume-title":"12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9--12, 2007, Proceedings (Lecture Notes in Computer Science)","volume":"4443","author":"Jiang Nan","year":"2007","unstructured":"Nan Jiang and Le Gruenwald. 2007. Estimating Missing Data in Data Streams. In Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9--12, 2007, Proceedings (Lecture Notes in Computer Science), Vol. 4443. Springer, 981--987."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430920"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377383"},{"key":"e_1_2_1_25_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24--26, 2017, Conference Track Proceedings. OpenReview.net. https:\/\/openreview.net\/forum?id=SJU4ayYgl"},{"key":"e_1_2_1_26_1","volume-title":"Data Imputation for Sparse Radio Maps in Indoor Positioning. In 39th IEEE International Conference on Data Engineering, ICDE 2023","author":"Li Xiao","year":"2023","unstructured":"Xiao Li, Huan Li, Harry Kai-Ho Chan, Hua Lu, and Christian S. Jensen. 2023. Data Imputation for Sparse Radio Maps in Indoor Positioning. In 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3--7, 2023. IEEE, 2235--2248."},{"key":"e_1_2_1_27_1","volume-title":"NAOMI: Non-Autoregressive Multiresolution Sequence Imputation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Liu Yukai","year":"2019","unstructured":"Yukai Liu, Rose Yu, Stephan Zheng, Eric Zhan, and Yisong Yue. 2019. NAOMI: Non-Autoregressive Multiresolution Sequence Imputation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada. 11236--11246."},{"key":"e_1_2_1_28_1","volume-title":"Multivariate Time Series Imputation with Generative Adversarial Networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Luo Yonghong","year":"2018","unstructured":"Yonghong Luo, Xiangrui Cai, Ying Zhang, Jun Xu, and Xiaojie Yuan. 2018. Multivariate Time Series Imputation with Generative Adversarial Networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montr\u00e9al, Canada. 1603--1614."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/429"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","volume":"70","author":"Mei Jiali","year":"2017","unstructured":"Jiali Mei, Yohann de Castro, Yannig Goude, and Georges H\u00e9brail. 2017. Non-negative Matrix Factorization for Time Series Recovery From a Few Temporal Aggregates. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6--11 August 2017 (Proceedings of Machine Learning Research), Vol. 70. PMLR, 2382--2390."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","volume":"80","author":"Mescheder Lars M.","year":"2018","unstructured":"Lars M. Mescheder, Andreas Geiger, and Sebastian Nowozin. 2018. Which Training Methods for GANs do actually Converge?. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018 (Proceedings of Machine Learning Research), Vol. 80. PMLR, 3478--3487."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i10.17086"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0382-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083674"},{"key":"e_1_2_1_35_1","volume-title":"Sellis","author":"Patroumpas Kostas","year":"2006","unstructured":"Kostas Patroumpas and Timos K. Sellis. 2006. Window Specification over Data Streams. In Current Trends in Database Technology - EDBT 2006, EDBT 2006 Workshops PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMA, and Reactivity on the Web, Munich, Germany, March 26--31, 2006, Revised Selected Papers (Lecture Notes in Computer Science), Vol. 4254. Springer, 445--464."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00577-6"},{"key":"e_1_2_1_37_1","volume-title":"On the Unreasonable Effectiveness of Feature Propagation in Learning on Graphs With Missing Node Features. In Learning on Graphs Conference, LoG 2022","volume":"198","author":"Rossi Emanuele","year":"2022","unstructured":"Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022. On the Unreasonable Effectiveness of Feature Propagation in Learning on Graphs With Missing Node Features. In Learning on Graphs Conference, LoG 2022, 9--12 December 2022, Virtual Event (Proceedings of Machine Learning Research), Vol. 198. PMLR, 11."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2020.06.005"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0261-7"},{"key":"e_1_2_1_40_1","volume-title":"EDBT 2019","author":"Traub Jonas","year":"2019","unstructured":"Jonas Traub, Philipp M. Grulich, Alejandro Rodriguez Cuellar, Sebastian Bre\u00df, Asterios Katsifodimos, Tilmann Rabl, and Volker Markl. 2019. Efficient Window Aggregation with General Stream Slicing. In Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26--29, 2019. OpenProceedings.org, 97--108."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.6.520"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34239-7"},{"key":"e_1_2_1_43_1","volume-title":"6th International Conference on Learning Representations, ICLR","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net. https:\/\/openreview.net\/forum?id=rJXMpikCZ"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564737"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017","author":"Wellenzohn Kevin","year":"2017","unstructured":"Kevin Wellenzohn, Michael H. B\u00f6hlen, Anton Dign\u00f6s, Johann Gamper, and Hannes Mitterer. 2017. Continuous Imputation of Missing Values in Streams of Pattern-Determining Time Series. In Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21--24, 2017. OpenProceedings.org, 330--341."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415562"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342269"},{"key":"e_1_2_1_48_1","volume-title":"Handling Missing Data with Graph Representation Learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"You Jiaxuan","year":"2020","unstructured":"Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel J. Kochenderfer, and Jure Leskovec. 2020. Handling Missing Data with Graph Representation Learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual."},{"key":"e_1_2_1_49_1","volume-title":"Dhillon","author":"Yu Hsiang-Fu","year":"2016","unstructured":"Hsiang-Fu Yu, Nikhil Rao, and Inderjit S. Dhillon. 2016. Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5--10, 2016, Barcelona, Spain. 847--855."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871750"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.05.073"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T14:09:12Z","timestamp":1707228552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632100"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632100","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2023-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}