{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T18:06:05Z","timestamp":1791482765771,"version":"4.3.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:p>Underlying many types of data analytics, a spatiotemporal quantile monitoring (SQM) query continuously returns the quantiles of a dataset observed in a spatiotemporal range. In this paper, we study SQM in an Internet of Things (IoT) based edge computing environment, where concurrent SQM queries share the same infrastructure asynchronously. To minimize query latency while providing result accuracy guarantees, we design a processing framework that virtualizes edge-resident data sketches for quantile computing. In the framework, a coordinator edge node manages edge sketches and synchronizes edge sketch processing and query executions. The co-ordinator also controls the processed data fractions of edge sketches, which helps to achieve the optimal latency with error-bounded results for each single query. To support concurrent queries, we employ a grid to decompose queries into subqueries and process them efficiently using shared edge sketches. We also devise a relaxation algorithm to converge to optimal latencies for those subqueries whose result errors are still bounded. We evaluate our proposals using two high-speed streaming datasets in a simulated IoT setting with edge nodes. The results show that our proposals achieve efficient, scalable, and error-bounded SQM.<\/jats:p>","DOI":"10.14778\/3538598.3538600","type":"journal-article","created":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T17:12:31Z","timestamp":1658941951000},"page":"1753-1765","source":"Crossref","is-referenced-by-count":7,"title":["Efficient and error-bounded spatiotemporal quantile monitoring in edge computing environments"],"prefix":"10.14778","volume":"15","author":[{"given":"Huan","family":"Li","sequence":"first","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lanjing","family":"Yi","sequence":"additional","affiliation":[{"name":"SUSTech, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"SUSTech, 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"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2019. 5G Xn interface protocol architecture. http:\/\/4g5gworld.com\/blog\/5g-xn-interface-protocol-architecture. (Accessed Jan 2022). 2019. 5G Xn interface protocol architecture. http:\/\/4g5gworld.com\/blog\/5g-xn-interface-protocol-architecture. (Accessed Jan 2022)."},{"key":"e_1_2_1_2_1","volume-title":"Generic IoT data simulator. https:\/\/github.com\/IBA-Group-IT\/IoT-data-simulator. (Accessed","year":"2021","unstructured":"2020. Generic IoT data simulator. https:\/\/github.com\/IBA-Group-IT\/IoT-data-simulator. (Accessed Sep 2021 ). 2020. Generic IoT data simulator. https:\/\/github.com\/IBA-Group-IT\/IoT-data-simulator. (Accessed Sep 2021)."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/en.wikipedia.org\/wiki\/5G. (Accessed","author":"Wikipedia G","year":"2021","unstructured":"2021. 5 G - Wikipedia . https:\/\/en.wikipedia.org\/wiki\/5G. (Accessed Jun 2021 ). 2021. 5G - Wikipedia. https:\/\/en.wikipedia.org\/wiki\/5G. (Accessed Jun 2021)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3046188"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Arvind Arasu and Gurmeet Singh Manku. 2004. Approximate counts and quantiles over sliding windows. In PODS. 286--296. Arvind Arasu and Gurmeet Singh Manku. 2004. Approximate counts and quantiles over sliding windows. In PODS. 286--296.","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_7_1","first-page":"59","article-title":"NG radio access network (NG-RAN)","volume":"6","author":"Bertenyi Balazs","year":"2018","unstructured":"Balazs Bertenyi , Richard Burbidge , Gino Masini , Sasha Sirotkin , and Yin Gao . 2018 . NG radio access network (NG-RAN) . J. ICT Stand 6 , 1 (2018), 59 -- 76 . Balazs Bertenyi, Richard Burbidge, Gino Masini, Sasha Sirotkin, and Yin Gao. 2018. NG radio access network (NG-RAN). J. ICT Stand 6, 1 (2018), 59--76.","journal-title":"J. ICT Stand"},{"key":"e_1_2_1_8_1","volume-title":"Distributed query processing in the edge assisted IoT data monitoring system","author":"Cai Zhipeng","year":"2020","unstructured":"Zhipeng Cai and Tuo Shi . 2020. Distributed query processing in the edge assisted IoT data monitoring system . IEEE Internet Things J. ( 2020 ). Zhipeng Cai and Tuo Shi. 2020. Distributed query processing in the edge assisted IoT data monitoring system. IEEE Internet Things J. (2020)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2487344"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2974919"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3080008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode Minos Garofalakis Shan Muthukrishnan and Rajeev Rastogi. 2005. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In SIGMOD. 25--36. Graham Cormode Minos Garofalakis Shan Muthukrishnan and Rajeev Rastogi. 2005. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In SIGMOD. 25--36.","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Vincenzo De Maio and Ivona Brandic. 2018. First hop mobile offloading of dag computations. In CCGRID. 83--92. Vincenzo De Maio and Ivona Brandic. 2018. First hop mobile offloading of dag computations. In CCGRID. 83--92.","DOI":"10.1109\/CCGRID.2018.00023"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Mayuresh Desai and Arati Phadke. 2017. Internet of Things based vehicle monitoring system. In WOCN. 1--3. Mayuresh Desai and Arati Phadke. 2017. Internet of Things based vehicle monitoring system. In WOCN. 1--3.","DOI":"10.1109\/WOCN.2017.8065840"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2014.6894452"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Michael B Greenwald and Sanjeev Khanna. 2004. Power-conserving computation of order-statistics over sensor networks. In PODS. 275--285. Michael B Greenwald and Sanjeev Khanna. 2004. Power-conserving computation of order-statistics over sensor networks. In PODS. 275--285.","DOI":"10.1145\/1055558.1055597"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Zaobo He Zhipeng Cai Siyao Cheng and Xiaoming Wang. 2014. Approximate aggregation for tracking quantiles in wireless sensor networks. In COCOA. 161--172. Zaobo He Zhipeng Cai Siyao Cheng and Xiaoming Wang. 2014. Approximate aggregation for tracking quantiles in wireless sensor networks. In COCOA. 161--172.","DOI":"10.1007\/978-3-319-12691-3_13"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2019.1701366"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Zengfeng Huang Lu Wang Ke Yi and Yunhao Liu. 2011. Sampling based algorithms for quantile computation in sensor networks. In SIGMOD. 745--756. Zengfeng Huang Lu Wang Ke Yi and Yunhao Liu. 2011. Sampling based algorithms for quantile computation in sensor networks. In SIGMOD. 745--756.","DOI":"10.1145\/1989323.1989401"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2787"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Zohar Karnin Kevin Lang and Edo Liberty. 2016. Optimal quantile approximation in streams. In FOCS. 71--78. Zohar Karnin Kevin Lang and Edo Liberty. 2016. Optimal quantile approximation in streams. In FOCS. 71--78.","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2015.2495145"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2019.2920908"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Jing Li Weifa Liang Meitian Huang and Xiahua Jia. 2019. Providing reliability-aware virtualized network function services for mobile edge computing. In ICDCS. 732--741. Jing Li Weifa Liang Meitian Huang and Xiahua Jia. 2019. Providing reliability-aware virtualized network function services for mobile edge computing. In ICDCS. 732--741.","DOI":"10.1109\/ICDCS.2019.00078"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2019.01.022"},{"key":"e_1_2_1_27_1","unstructured":"Xuemin Lin Hongjun Lu Jian Xu and Jeffrey Xu Yu. 2004. Continuously maintaining quantile summaries of the most recent N elements over a data stream. In ICDE. 362--373. Xuemin Lin Hongjun Lu Jian Xu and Jeffrey Xu Yu. 2004. Continuously maintaining quantile summaries of the most recent N elements over a data stream. In ICDE. 362--373."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2019.2935738"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2682318"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Gurmeet Singh Manku Sridhar Rajagopalan and Bruce G Lindsay. 1998. Approximate medians and other quantiles in one pass and with limited memory. In SIGMOD. 426--435. Gurmeet Singh Manku Sridhar Rajagopalan and Bruce G Lindsay. 1998. Approximate medians and other quantiles in one pass and with limited memory. In SIGMOD. 426--435.","DOI":"10.1145\/276305.276342"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304204"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Yuyi Mao Jun Zhang SH Song and Khaled Ben Letaief. 2016. Power-delay tradeoff in multi-user mobile-edge computing systems. In GLOBECOM. 1--6. Yuyi Mao Jun Zhang SH Song and Khaled Ben Letaief. 2016. Power-delay tradeoff in multi-user mobile-edge computing systems. In GLOBECOM. 1--6.","DOI":"10.1109\/GLOCOM.2016.7842160"},{"key":"e_1_2_1_33_1","first-page":"237","article-title":"Cost-based quantile query processing in wireless sensor networks","volume":"1","author":"Niedermayer Johannes","year":"2013","unstructured":"Johannes Niedermayer , Mario A Nascimento , Matthias Renz , Peer Kr\u00f6ger , Khaled Ammar , and Hans-Peter Kriegel . 2013 . Cost-based quantile query processing in wireless sensor networks . In MDM , Vol. 1. 237 -- 246 . Johannes Niedermayer, Mario A Nascimento, Matthias Renz, Peer Kr\u00f6ger, Khaled Ammar, and Hans-Peter Kriegel. 2013. Cost-based quantile query processing in wireless sensor networks. In MDM, Vol. 1. 237--246.","journal-title":"MDM"},{"key":"e_1_2_1_34_1","unstructured":"Johannes Niedermayer Mario A Nascimento Matthias Renz Peer Kr\u00f6ger and Hans-Peter Kriegel. 2014. Continuous quantile query processing in wireless Sensor networks. In EDBT. 247--258. Johannes Niedermayer Mario A Nascimento Matthias Renz Peer Kr\u00f6ger and Hans-Peter Kriegel. 2014. Continuous quantile query processing in wireless Sensor networks. In EDBT. 247--258."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/VTCFall.2015.7391144"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Hui Peng Xiaoying Zhang Hong Chen Yao Wu Juru Zeng and Deying Li. 2015. Enable privacy preservation for k-NN query in two-tiered wireless sensor networks. In ICC. 6289--6294. Hui Peng Xiaoying Zhang Hong Chen Yao Wu Juru Zeng and Deying Li. 2015. Enable privacy preservation for k-NN query in two-tiered wireless sensor networks. In ICC. 6289--6294.","DOI":"10.1109\/ICC.2015.7249326"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Jan Plachy Zdenek Becvar and Emilio Calvanese Strinati. 2016. Dynamic resource allocation exploiting mobility prediction in mobile edge computing. In PIMRC. 1--6. Jan Plachy Zdenek Becvar and Emilio Calvanese Strinati. 2016. Dynamic resource allocation exploiting mobility prediction in mobile edge computing. In PIMRC. 1--6.","DOI":"10.1109\/PIMRC.2016.7794955"},{"key":"e_1_2_1_38_1","volume-title":"Priyanka Chidambar Patil, Thrishna Palissery, and Kaikai Liu.","author":"Sangolli Deepa Rajendra","year":"2019","unstructured":"Deepa Rajendra Sangolli , Nagthej Manangi Ravindrarao , Priyanka Chidambar Patil, Thrishna Palissery, and Kaikai Liu. 2019 . Enabling high availability edge computing platform. In MobileCloud . 85--92. Deepa Rajendra Sangolli, Nagthej Manangi Ravindrarao, Priyanka Chidambar Patil, Thrishna Palissery, and Kaikai Liu. 2019. Enabling high availability edge computing platform. In MobileCloud. 85--92."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Bo Sheng and Qun Li. 2008. Verifiable privacy-preserving range query in two-tiered sensor networks. In INFOCOM. 46--50. Bo Sheng and Qun Li. 2008. Verifiable privacy-preserving range query in two-tiered sensor networks. In INFOCOM. 46--50.","DOI":"10.1109\/INFOCOM.2008.18"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Jing Shi Rui Zhang and Yanchao Zhang. 2009. Secure range queries in tiered sensor networks. In INFOCOM. 945--953. Jing Shi Rui Zhang and Yanchao Zhang. 2009. Secure range queries in tiered sensor networks. In INFOCOM. 945--953.","DOI":"10.1109\/INFCOM.2009.5062005"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2010.102210.100548"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2016.2579198"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Nisheeth Shrivastava Chiranjeeb Buragohain Divyakant Agrawal and Subhash Suri. 2004. Medians and beyond: New aggregation techniques for sensor networks. In SenSys. 239--249. Nisheeth Shrivastava Chiranjeeb Buragohain Divyakant Agrawal and Subhash Suri. 2004. Medians and beyond: New aggregation techniques for sensor networks. In SenSys. 239--249.","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.3493"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2019.2901346"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Tarik Taleb and Adlen Ksentini. 2013. An analytical model for follow me cloud. In GLOBECOM. 1291--1296. Tarik Taleb and Adlen Ksentini. 2013. An analytical model for follow me cloud. In GLOBECOM. 1291--1296.","DOI":"10.1109\/GLOCOM.2013.6831252"},{"key":"e_1_2_1_47_1","unstructured":"Yufei Tao George Kollios Jeffrey Considine Feifei Li and Dimitris Papadias. 2004. Spatio-temporal aggregation using sketches. In ICDE. 214--225. Yufei Tao George Kollios Jeffrey Considine Feifei Li and Dimitris Papadias. 2004. Spatio-temporal aggregation using sketches. In ICDE. 214--225."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Daniel Ting Jonathan Malkin and Lee Rhodes. 2020. Data sketching for real time analytics: Theory and practice. In KDD. 3567--3568. Daniel Ting Jonathan Malkin and Lee Rhodes. 2020. Data sketching for real time analytics: Theory and practice. In KDD. 3567--3568.","DOI":"10.1145\/3394486.3406480"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.iot.2021.100428"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Michal Vondra and Zdenek Becvar. 2014. QoS-ensuring distribution of computation load among cloud-enabled small cells. In CloudNet. 197--203. Michal Vondra and Zdenek Becvar. 2014. QoS-ensuring distribution of computation load among cloud-enabled small cells. In CloudNet. 197--203.","DOI":"10.1109\/CloudNet.2014.6968992"},{"key":"e_1_2_1_51_1","unstructured":"Runhua Xu Balaji Palanisamy and James Joshi. 2018. QueryGuard: Privacy-preserving latency-aware query optimization for edge computing. In Trust-Com\/BigDataSE. 1097--1106. Runhua Xu Balaji Palanisamy and James Joshi. 2018. QueryGuard: Privacy-preserving latency-aware query optimization for edge computing. In Trust-Com\/BigDataSE. 1097--1106."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2012.02.003"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Changsheng You and Kaibin Huang. 2016. Multiuser resource allocation for mobile-edge computation offloading. In GLOBECOM. 1--6. Changsheng You and Kaibin Huang. 2016. Multiuser resource allocation for mobile-edge computation offloading. In GLOBECOM. 1--6.","DOI":"10.1109\/GLOCOM.2016.7842016"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0130-z"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2018.2867482"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Rui Zhang Jing Shi Yunzhong Liu and Yanchao Zhang. 2010. Verifiable fine-grained top-k queries in tiered sensor networks. In INFOCOM. 1--9. Rui Zhang Jing Shi Yunzhong Liu and Yanchao Zhang. 2010. Verifiable fine-grained top-k queries in tiered sensor networks. In INFOCOM. 1--9.","DOI":"10.1109\/INFCOM.2010.5461927"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450990"},{"key":"e_1_2_1_58_1","first-page":"32","article-title":"GeoLife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng Yu","year":"2010","unstructured":"Yu Zheng , Xing Xie , Wei-Ying Ma , 2010 . GeoLife: A collaborative social networking service among user, location and trajectory . IEEE Data Eng. Bull. 33 , 2 (2010), 32 -- 39 . Yu Zheng, Xing Xie, Wei-Ying Ma, et al. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33, 2 (2010), 32--39.","journal-title":"IEEE Data Eng. Bull."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3538598.3538600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:39:16Z","timestamp":1727656756000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3538598.3538600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5]]},"references-count":58,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["10.14778\/3538598.3538600"],"URL":"https:\/\/doi.org\/10.14778\/3538598.3538600","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,5]]}}}