{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:27Z","timestamp":1750308867379,"version":"3.41.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["688380"],"award-info":[{"award-number":["688380"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["619491, 619435"],"award-info":[{"award-number":["619491, 619435"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>As data becomes dynamic, large, and distributed, there is increasing demand for what have become known as<jats:italic>distributed stream algorithms<\/jats:italic>. Since continuously collecting the data to a central server and processing it there is infeasible, a common approach is to define<jats:italic>local<\/jats:italic>conditions at the distributed nodes, such that\u2014as long as they are maintained\u2014some desirable<jats:italic>global<\/jats:italic>condition holds.<\/jats:p><jats:p>Previous methods derived local conditions focusing on communication efficiency. While proving very useful for reducing the communication volume, these local conditions often suffer from heavy computational burden at the nodes. The computational complexity of the local conditions affects both the runtime and the energy consumption. These are especially critical for resource-limited devices like smartphones and sensor nodes. Such devices are becoming more ubiquitous due to the recent trend toward smart cities and the Internet of Things. To accommodate for high data rates and limited resources of these devices, it is crucial that the local conditions be quickly and efficiently evaluated.<\/jats:p><jats:p>Here we propose a novel approach, designated CB (for Convex\/Concave Bounds). CB defines local conditions using suitably chosen convex and concave functions. Lightweight and simple, these local conditions can be rapidly checked on the fly. CB\u2019s superiority over the state-of-the-art is demonstrated in its reduced runtime and power consumption, by up to six orders of magnitude in some cases. As an added bonus, CB also reduced communication overhead in all the tested application scenarios.<\/jats:p>","DOI":"10.1145\/3226113","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Lightweight Monitoring of Distributed Streams"],"prefix":"10.1145","volume":"43","author":[{"given":"Arnon","family":"Lazerson","sequence":"first","affiliation":[{"name":"Technion \u2013 Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Keren","sequence":"additional","affiliation":[{"name":"University of Haifa, Israel, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[{"name":"Technion \u2013 Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Amir Ali Ahmadi and Georgina Hall. 2015. DC decomposition of nonconvex polynomials with algebraic techniques. Mathematical Programming (2015) 1--26. Amir Ali Ahmadi and Georgina Hall. 2015. DC decomposition of nonconvex polynomials with algebraic techniques. Mathematical Programming (2015) 1--26."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603884"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.06.004"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef T. S. Jayram Ravi Kumar D. Sivakumar and Luca Trevisan. 2002. Counting distinct elements in a data stream. In RANDOM. 1--10. Ziv Bar-Yossef T. S. Jayram Ravi Kumar D. Sivakumar and Luca Trevisan. 2002. Counting distinct elements in a data stream. In RANDOM. 1--10.","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3115\/1225403.1225421"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press. S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.31"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.85"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481528.2481530"},{"key":"e_1_2_1_12_1","unstructured":"Graham Cormode and Minos N. Garofalakis. 2005. Sketching streams through the net: Distributed approximate query tracking. In VLDB. 13--24. Graham Cormode and Minos N. Garofalakis. 2005. Sketching streams through the net: Distributed approximate query tracking. In VLDB. 13--24."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366106"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Abhinandan Das Sumit Ganguly Minos N. Garofalakis and Rajeev Rastogi. 2004. Distributed set expression cardinality estimation. In VLDB. 312--323. Abhinandan Das Sumit Ganguly Minos N. Garofalakis and Rajeev Rastogi. 2004. Distributed set expression cardinality estimation. In VLDB. 312--323.","DOI":"10.1016\/B978-012088469-8.50030-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2002.1003034"},{"key":"e_1_2_1_16_1","unstructured":"Manfredo P. Do Carmo. 2016. Differential Geometry of Curves and Surfaces: Revised and Updated (2nd ed.). Courier Dover Publications. Manfredo P. Do Carmo. 2016. Differential Geometry of Curves and Surfaces: Revised and Updated (2nd ed.). Courier Dover Publications."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.35.11.652"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Arik Friedman Izchak Sharfman Daniel Keren and Assaf Schuster. 2014. Privacy-preserving distributed stream monitoring. In NDSS. 1--12. Arik Friedman Izchak Sharfman Daniel Keren and Assaf Schuster. 2014. Privacy-preserving distributed stream monitoring. In NDSS. 1--12.","DOI":"10.14722\/ndss.2014.23128"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783349"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098092"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536220"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602137"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213867"},{"key":"e_1_2_1_25_1","unstructured":"G. H. Golub and C. F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press. G. H. Golub and C. F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536357"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780802699201"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ling Huang Michael I. Jordan Anthony Joseph Minos Garofalakis and Nina Taft. 2006. In-network PCA and anomaly detection. In In NIPS. 617--624. Ling Huang Michael I. Jordan Anthony Joseph Minos Garofalakis and Nina Taft. 2006. In-network PCA and anomaly detection. In In NIPS. 617--624.","DOI":"10.7551\/mitpress\/7503.003.0082"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.24"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Antonios Igglezakis Antonios Deligiannakis and Aggelos Bletsas. 2014. Geometric monitoring for CSI reduction in amplify-and-forward relay networks. In ICASSP. 2729--2733. Antonios Igglezakis Antonios Deligiannakis and Aggelos Bletsas. 2014. Geometric monitoring for CSI reduction in amplify-and-forward relay networks. In ICASSP. 2729--2733.","DOI":"10.1109\/ICASSP.2014.6854096"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2015.2437951"},{"key":"e_1_2_1_32_1","unstructured":"S. Ratnasamy Jain J. M. Hellerstein and D. Wetherall. 2004. A wakeup call for internet monitoring systems: The case for distributed triggers. In HotNets-III. 1--6. S. Ratnasamy Jain J. M. Hellerstein and D. Wetherall. 2004. A wakeup call for internet monitoring systems: The case for distributed triggers. In HotNets-III. 1--6."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2013.2296516"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497525"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497461"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.180"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.102"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015492"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093742.3093918"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939820"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735487"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005345"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559885"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339692"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061322"},{"volume-title":"Proceedings of the VLDB Endowment. 637--648","year":"2005","author":"Michel Sebastian","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-247X(02)00719-9"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.24102\/ijes.v1i1.39"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Themis Palpanas. 2013. Real-time data analytics in sensor networks. In Managing and Mining Sensor Data. 173--210. Themis Palpanas. 2013. Real-time data analytics in sensor networks. In Managing and Mining Sensor Data. 173--210.","DOI":"10.1007\/978-1-4614-6309-2_7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959074"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Odysseas Papapetrou and Minos Garofalakis. 2014. Continuous fragmented skylines over distributed streams. In ICDE. 124--135. Odysseas Papapetrou and Minos Garofalakis. 2014. Continuous fragmented skylines over distributed streams. In ICDE. 124--135.","DOI":"10.1109\/ICDE.2014.6816645"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Jeff M. Phillips Elad Verbin and Qin Zhang. 2012. Lower bounds for number-in-hand multiparty communication complexity made easy. In SODA. 486--501. Jeff M. Phillips Elad Verbin and Qin Zhang. 2012. Lower bounds for number-in-hand multiparty communication complexity made easy. In SODA. 486--501.","DOI":"10.1137\/1.9781611973099.42"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2011.2170080"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921072"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497513"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"IzchaK. Sharfman Assaf Schuster and Daniel Keren. 2007. Aggregate threshold queries in sensor networks. In IPDPS. 1--10. IzchaK. Sharfman Assaf Schuster and Daniel Keren. 2007. Aggregate threshold queries in sensor networks. In IPDPS. 1--10.","DOI":"10.1109\/IPDPS.2007.370297"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292613"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376958"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.2307\/3029337"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.34"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767387"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.169"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1142\/6023"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","unstructured":"Gal Yehuda Daniel Keren and Islam Akaria. 2017. Monitoring properties of large distributed dynamic graphs. In IPDPS. 2--11. Gal Yehuda Daniel Keren and Islam Akaria. 2017. Monitoring properties of large distributed dynamic graphs. In IPDPS. 2--11.","DOI":"10.1109\/IPDPS.2017.123"},{"key":"e_1_2_1_67_1","unstructured":"B.-K. Yi Nikolaos D. Sidiropoulos Theodore Johnson H. V. Jagadish Christos Faloutsos and Alexandros Biliris. 2000. Online data mining for co-evolving time sequences. In ICDE. 13--22. B.-K. Yi Nikolaos D. Sidiropoulos Theodore Johnson H. V. Jagadish Christos Faloutsos and Alexandros Biliris. 2000. Online data mining for co-evolving time sequences. In ICDE. 13--22."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287401"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3226113","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3226113","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:15:08Z","timestamp":1750281308000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3226113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3226113"],"URL":"https:\/\/doi.org\/10.1145\/3226113","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}