{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,8]],"date-time":"2024-05-08T17:52:44Z","timestamp":1715190764551},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Median absolute deviation (MAD), the median of the absolute deviations from the median, has been found useful in various applications such as outlier detection. Together with median, MAD is more robust to abnormal data than mean and standard deviation (SD). Unfortunately, existing methods return only approximate MAD that may be far from the exact one, and thus mislead the downstream applications. Computing exact MAD is costly, however, especially in space, by storing the entire dataset in memory. In this paper, we propose COnstruction-REfinement Sketch (CORE-Sketch) for computing exact MAD. The idea is to construct some sketch within limited space, and gradually refine the sketch to find the MAD element, i.e., the element with distance to the median exactly equal to MAD. Mergeability and convergence of the method is analyzed, ensuring the correctness of the proposal and enabling parallel computation. Extensive experiments demonstrate that CORE-Sketch achieves significantly less space occupation compared to the aforesaid baseline of No-Sketch, and has time and space costs relatively comparable to the DD-Sketch method for approximate MAD.<\/jats:p>","DOI":"10.14778\/3611479.3611491","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"2832-2844","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space"],"prefix":"10.14778","volume":"16","author":[{"given":"Haoquan","family":"Guan","sequence":"first","affiliation":[{"name":"BNRist, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziling","family":"Chen","sequence":"additional","affiliation":[{"name":"BNRist, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaoxu","family":"Song","sequence":"additional","affiliation":[{"name":"BNRist, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190659"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-020-9708-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476266"},{"key":"e_1_2_1_5_1","unstructured":"Source code and full version technical report for CORE-Sketch. 2023. https:\/\/github.com\/thssdb\/core-sketch.  Source code and full version technical report for CORE-Sketch. 2023. https:\/\/github.com\/thssdb\/core-sketch."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458323"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1974.10482962"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_9_1","unstructured":"Configuration in Apache IoTDB. 2023. https:\/\/iotdb.apache.org\/UserGuide\/Master\/Reference\/Common-Config-Manual.html.  Configuration in Apache IoTDB. 2023. https:\/\/iotdb.apache.org\/UserGuide\/Master\/Reference\/Common-Config-Manual.html."},{"key":"e_1_2_1_10_1","unstructured":"Implementation in Apache IoTDB. 2023. https:\/\/github.com\/apache\/iotdb\/tree\/research\/core-sketch.  Implementation in Apache IoTDB. 2023. https:\/\/github.com\/apache\/iotdb\/tree\/research\/core-sketch."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0051-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2788611"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00070"},{"key":"e_1_2_1_14_1","volume-title":"MCUNet: Tiny Deep Learning on IoT Devices. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Lin Ji","year":"2020","unstructured":"Ji Lin , Wei-Ming Chen , Yujun Lin , John Cohn , Chuang Gan , and Song Han . 2020 . MCUNet: Tiny Deep Learning on IoT Devices. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/86c51678350f656dcc7f490a43946ee5-Abstract.html Ji Lin, Wei-Ming Chen, Yujun Lin, John Cohn, Chuang Gan, and Song Han. 2020. MCUNet: Tiny Deep Learning on IoT Devices. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/86c51678350f656dcc7f490a43946ee5-Abstract.html"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389136"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352135"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559965"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551830"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0895-7177(01)00109-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00150-B"},{"key":"e_1_2_1_21_1","unstructured":"MAD query in InfluxDB. 2023. https:\/\/docs.influxdata.com\/flux\/v0.x\/stdlib\/contrib\/anaisdg\/anomalydetection\/mad.  MAD query in InfluxDB. 2023. https:\/\/docs.influxdata.com\/flux\/v0.x\/stdlib\/contrib\/anaisdg\/anomalydetection\/mad."},{"key":"e_1_2_1_22_1","unstructured":"MAD query in IoTDB. 2023. https:\/\/iotdb.apache.org\/UserGuide\/Master\/Operators-Functions\/Data-Profiling.html#mad.  MAD query in IoTDB. 2023. https:\/\/iotdb.apache.org\/UserGuide\/Master\/Operators-Functions\/Data-Profiling.html#mad."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-022-00185-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694428.2694435"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450990"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:15:45Z","timestamp":1695507345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":25,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611491"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611491","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}