{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:31:39Z","timestamp":1773192699317,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>Missing values are common in data analysis and present a usability challenge. Users are forced to pick between removing tuples with missing values or creating a cleaned version of their data by applying a relatively expensive imputation strategy. Our system, ImputeDB, incorporates imputation into a cost-based query optimizer, performing necessary imputations on-the-fly for each query. This allows users to immediately explore their data, while the system picks the optimal placement of imputation operations. We evaluate this approach on three real-world survey-based datasets. Our experiments show that our query plans execute between 10 and 140 times faster than first imputing the base tables. Furthermore, we show that the query results from on-the-fly imputation differ from the traditional base-table imputation approach by 0--8%. Finally, we show that while dropping tuples with missing values that fail query constraints discards 6--78% of the data, on-the-fly imputation loses only 0--21%.<\/jats:p>","DOI":"10.14778\/3137628.3137641","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1310-1321","source":"Crossref","is-referenced-by-count":32,"title":["Query optimization for dynamic imputation"],"prefix":"10.14778","volume":"10","author":[{"given":"Jos\u00e9","family":"Cambronero","sequence":"first","affiliation":[{"name":"MIT CSAIL"}]},{"given":"John K.","family":"Feser","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}]},{"given":"Micah J.","family":"Smith","sequence":"additional","affiliation":[{"name":"MIT LIDS"}]},{"given":"Samuel","family":"Madden","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"6\n   .830 Lab 1: SimpleDB. url: http:\/\/db.csail.mit.edu\/6.830\/assignments\/lab1.html. 6.830 Lab 1: SimpleDB. url: http:\/\/db.csail.mit.edu\/6.830\/assignments\/lab1.html."},{"key":"e_1_2_1_2_1","volume-title":"An Empirical Comparison of Multiple Imputation Methods for Categorical Data\". In: arXiv:1508.05918","author":"Akande O.","year":"2015","unstructured":"O. Akande , F. Li , \" An Empirical Comparison of Multiple Imputation Methods for Categorical Data\". In: arXiv:1508.05918 ( 2015 ). O. Akande, F. Li, et al. \"An Empirical Comparison of Multiple Imputation Methods for Categorical Data\". In: arXiv:1508.05918 (2015)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.201.0041"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/aje\/kwq260"},{"issue":"3","key":"e_1_2_1_5_1","first-page":"1","article-title":"van Buuren and K. Groothuis-Oudshoorn. \"mice: Multivariate Imputation by Chained Equations in R","volume":"45","author":"S","year":"2011","unstructured":"S . van Buuren and K. Groothuis-Oudshoorn. \"mice: Multivariate Imputation by Chained Equations in R \". In: Journal of Statistical Software 45 . 3 ( 2011 ), pp. 1 -- 67 . S. van Buuren and K. Groothuis-Oudshoorn. \"mice: Multivariate Imputation by Chained Equations in R\". In: Journal of Statistical Software 45.3 (2011), pp. 1--67.","journal-title":"Journal of Statistical Software"},{"key":"e_1_2_1_6_1","unstructured":"Center for Disease Control. National Health and Nutrition Examination Survey (2013--2014). https:\/\/wwwn.cdc.gov\/nchs\/nhanes\/ContinuousNhanes\/Default.aspx?BeginYear=2013. Accessed: 2016-09-03.  Center for Disease Control. National Health and Nutrition Examination Survey (2013--2014). https:\/\/wwwn.cdc.gov\/nchs\/nhanes\/ContinuousNhanes\/Default.aspx?BeginYear=2013. Accessed: 2016-09-03."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/983055.983059"},{"key":"e_1_2_1_8_1","first-page":"711","volume-title":"VLDB '07","author":"Duan S.","year":"2007","unstructured":"S. Duan and S. Babu . \" Processing Forecasting Queries \". In: VLDB '07 . VLDB Endowment , 2007 , pp. 711 -- 722 . S. Duan and S. Babu. \"Processing Forecasting Queries\". In: VLDB '07. VLDB Endowment, 2007, pp. 711--722."},{"key":"e_1_2_1_9_1","volume-title":"Inter-Operator Feedback in Data Stream Management Systems via Punctuation","author":"Fern\u00e1ndez-Moctezuma R.","year":"2009","unstructured":"R. Fern\u00e1ndez-Moctezuma , K. Tufte , \" Inter-Operator Feedback in Data Stream Management Systems via Punctuation \". In : CIDR. 2009 . R. Fern\u00e1ndez-Moctezuma, K. Tufte, et al. \"Inter-Operator Feedback in Data Stream Management Systems via Punctuation\". In: CIDR. 2009."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13222-012-0108-4"},{"key":"e_1_2_1_11_1","unstructured":"FreeCodeCamp. 2016 New Coder Survey. https:\/\/www.kaggle.com\/freecodecamp\/2016-new-coder-survey-. Accessed: 2016-09-03.  FreeCodeCamp. 2016 New Coder Survey. https:\/\/www.kaggle.com\/freecodecamp\/2016-new-coder-survey-. Accessed: 2016-09-03."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790942"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90013-8"},{"key":"e_1_2_1_14_1","volume-title":"United Nations Economic Commission for Europe (UNECE)","author":"Hellerstein J. M.","year":"2008","unstructured":"J. M. Hellerstein . \"Quantitative data cleaning for large databases\". In: United Nations Economic Commission for Europe (UNECE) ( 2008 ). J. M. Hellerstein. \"Quantitative data cleaning for large databases\". In: United Nations Economic Commission for Europe (UNECE) (2008)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021564703268"},{"key":"e_1_2_1_16_1","first-page":"1137","volume-title":"IJCAI.","author":"Kohavi R.","year":"1995","unstructured":"R. Kohavi \" A study of cross-validation and bootstrap for accuracy estimation and model selection \". In: IJCAI. Vol. 14 . 2. Stanford , CA. 1995 , pp. 1137 -- 1145 . R. Kohavi et al. \"A study of cross-validation and bootstrap for accuracy estimation and model selection\". In: IJCAI. Vol. 14. 2. Stanford, CA. 1995, pp. 1137--1145."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-2070(00)00057-1"},{"key":"e_1_2_1_18_1","volume-title":"BayesDB: A probabilistic programming system for querying the probable implications of data\". In: arXiv:1512.05006","author":"Mansinghka V.","year":"2015","unstructured":"V. Mansinghka , R. Tibbetts , \" BayesDB: A probabilistic programming system for querying the probable implications of data\". In: arXiv:1512.05006 ( 2015 ). V. Mansinghka, R. Tibbetts, et al. \"BayesDB: A probabilistic programming system for querying the probable implications of data\". In: arXiv:1512.05006 (2015)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","DOI":"10.3917\/droz.paret.1964.01","volume-title":"Cours d'\u00e9conomie politique","author":"Pareto V.","year":"1964","unstructured":"V. Pareto . Cours d'\u00e9conomie politique . Vol. 1 . Librairie Droz , 1964 . V. Pareto. Cours d'\u00e9conomie politique. Vol. 1. Librairie Droz, 1964."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2013.01.010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050266.2050301"},{"key":"e_1_2_1_22_1","volume-title":"Programs for Machine Learning","author":"Quinlan J. R.","year":"1993","unstructured":"J. R. Quinlan . C4.5 : Programs for Machine Learning . San Francisco, CA, USA : Morgan Kaufmann Publishers Inc ., 1993 . J. R. Quinlan. C4.5: Programs for Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1993."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/63.3.581"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735512"},{"key":"e_1_2_1_25_1","volume-title":"Morgan Kaufmann","author":"Witten I. H.","year":"2016","unstructured":"I. H. Witten , E. Frank , : Practical machine learning tools and techniques . Morgan Kaufmann , 2016 . I. H. Witten, E. Frank, et al. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 2016."},{"key":"e_1_2_1_26_1","first-page":"651","volume-title":"VLDB '07","author":"Wolf G.","year":"2007","unstructured":"G. Wolf , H. Khatri , processing over incomplete autonomous databases \". In: VLDB '07 . VLDB Endowment. 2007 , pp. 651 -- 662 . G. Wolf, H. Khatri, et al. \"Query processing over incomplete autonomous databases\". In: VLDB '07. VLDB Endowment. 2007, pp. 651--662."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824055"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:59:32Z","timestamp":1672221572000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":27,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137641"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137641","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}