{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:57Z","timestamp":1775638437550,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T00:00:00Z","timestamp":1632787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Plan","award":["2019YFB1705301, 2019YFB1707001"],"award-info":[{"award-number":["2019YFB1705301, 2019YFB1707001"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072265, 71690231"],"award-info":[{"award-number":["62072265, 71690231"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MIIT High Quality Development Program 2020, NSF","award":["III-1763325, III-1909323, and SaTC-1930941"],"award-info":[{"award-number":["III-1763325, III-1909323, and SaTC-1930941"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            Stream data are often dirty, for example, owing to unreliable sensor reading or erroneous extraction of stock prices. Most stream data cleaning approaches employ a smoothing filter, which may seriously alter the data without preserving the original information. We argue that the cleaning should avoid changing those originally correct\/clean data, a.k.a. the\n            <jats:italic>minimum modification rule<\/jats:italic>\n            in data cleaning. To capture the knowledge about\n            <jats:italic>what is clean<\/jats:italic>\n            , we consider the (widely existing) constraints on the speed and acceleration of data changes, such as fuel consumption per hour, daily limit of stock prices, or the top speed and acceleration of a car. Guided by these semantic constraints, in this article, we propose the constraint-based approach for cleaning stream data. It is notable that existing data repair techniques clean (a sequence of) data\n            <jats:italic>as a whole<\/jats:italic>\n            and fail to support stream computation. To this end, we have to relax the global optimum over the entire sequence to the local optimum in a window. Rather than the commonly observed NP-hardness of general data repairing problems, our major contributions include (1) polynomial time algorithm for global optimum, (2) linear time algorithm towards local optimum under an efficient\n            <jats:italic>median-based solution<\/jats:italic>\n            , and (3) experiments on real datasets demonstrate that our method can show significantly lower L1 error than the existing approaches such as smoother.\n          <\/jats:p>","DOI":"10.1145\/3465740","type":"journal-article","created":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T20:52:15Z","timestamp":1632862335000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Stream Data Cleaning under Speed and Acceleration Constraints"],"prefix":"10.1145","volume":"46","author":[{"given":"Shaoxu","family":"Song","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Gao","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aoqian","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianmin","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip S.","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,28]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1627","article-title":"Smoothing and differentiation of data by simplified least-squares procedures","volume":"8","author":"Golay A.","year":"1964","unstructured":"A. Savitzky A. and M. J. E. Golay . 1964 . Smoothing and differentiation of data by simplified least-squares procedures . Analyt. Chem. 8 , 36 (1964), 1627 \u2013 1639 . DOI:http:\/\/dx.doi.org\/10.1021\/ac60214a047 A. Savitzky A. and M. J. E. Golay.1964. Smoothing and differentiation of data by simplified least-squares procedures. Analyt. Chem. 8, 36 (1964), 1627\u20131639. DOI:http:\/\/dx.doi.org\/10.1021\/ac60214a047","journal-title":"Analyt. Chem."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856328"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850579"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920870"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066175"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/501124"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_9_1","volume-title":"Gaussian kernel smoothing. CoRR abs\/2007.09539","author":"Chung Moo K.","year":"2020","unstructured":"Moo K. Chung . 2020. Gaussian kernel smoothing. CoRR abs\/2007.09539 ( 2020 ). Moo K. Chung. 2020. Gaussian kernel smoothing. CoRR abs\/2007.09539 (2020)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978068"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316741"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739068"},{"key":"e_1_2_1_13_1","volume-title":"Statistics","author":"Freedman David","unstructured":"David Freedman . 1991. Statistics ( 2 nd ed.). Norton . David Freedman. 1991. Statistics (2nd ed.). Norton.","edition":"2"},{"key":"e_1_2_1_14_1","volume-title":"International Encyclopedia of Statistical Science. 488\u2013490. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_244","author":"Fried Roland","unstructured":"Roland Fried and Ann Cathrice George . 2011. Exponential and holt-winters smoothing . In International Encyclopedia of Statistical Science. 488\u2013490. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_244 Roland Fried and Ann Cathrice George. 2011. Exponential and holt-winters smoothing. In International Encyclopedia of Statistical Science. 488\u2013490. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_244"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687693"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11748625_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164143"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514901"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448943"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463715"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196980"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367867"},{"key":"e_1_2_1_26_1","volume-title":"International Encyclopedia of Statistical Science. 1378\u20131379. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_535","author":"Sekander Hayat","unstructured":"Sekander Hayat Khan M.2011. Standard deviation . In International Encyclopedia of Statistical Science. 1378\u20131379. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_535 Sekander Hayat Khan M.2011. Standard deviation. In International Encyclopedia of Statistical Science. 1378\u20131379. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_535"},{"key":"e_1_2_1_27_1","first-page":"387","article-title":"Introduction to random signal analysis and Kalman filtering","volume":"22","author":"Mahalanabis A. K.","year":"1986","unstructured":"A. K. Mahalanabis . 1986 . Introduction to random signal analysis and Kalman filtering : Robert G. Brown. Autom. 22 , 3 (1986), 387 \u2013 388 . DOI:DOI:https:\/\/doi.org\/10.1016\/0005-1098(86)90041-5 A. K. Mahalanabis. 1986. Introduction to random signal analysis and Kalman filtering: Robert G. Brown. Autom. 22, 3 (1986), 387\u2013388. DOI:DOI:https:\/\/doi.org\/10.1016\/0005-1098(86)90041-5","journal-title":"Robert G. Brown. Autom."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137645"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3153490"},{"key":"e_1_2_1_31_1","volume-title":"International Encyclopedia of Statistical Science. 283\u2013284. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_183","author":"Smithson Michael","unstructured":"Michael Smithson . 2011. Confidence interval . In International Encyclopedia of Statistical Science. 283\u2013284. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_183 Michael Smithson. 2011. Confidence interval. In International Encyclopedia of Statistical Science. 283\u2013284. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-04898-2_183"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723730"},{"key":"e_1_2_1_33_1","volume-title":"Exploratory Data Analysis","author":"Tukey John W.","unstructured":"John W. Tukey . 1977. Exploratory Data Analysis . Addison-Wesley . Retrieved from https:\/\/www.worldcat.org\/oclc\/03058187. John W. Tukey. 1977. Exploratory Data Analysis. Addison-Wesley. Retrieved from https:\/\/www.worldcat.org\/oclc\/03058187."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2740926"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.83"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115410"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2990508"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.45"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465740","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:18Z","timestamp":1750191498000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,28]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3465740"],"URL":"https:\/\/doi.org\/10.1145\/3465740","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,28]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}