{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T02:00:35Z","timestamp":1705456835439},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>\n            Emerging large-scale monitoring applications rely on continuous tracking of complex data-analysis queries over collections of massive, physically-distributed data streams. Thus, in addition to the space- and time-efficiency requirements of conventional stream processing (at each remote monitor site), effective solutions also need to guarantee communication efficiency (over the underlying communication network). The complexity of the monitored query adds to the difficulty of the problem --- this is especially true for non-linear queries (e.g., joins), where no obvious solutions exist for distributing the monitored condition across sites. The recently proposed geometric method, based on the notion of covering spheres, offers a generic methodology for splitting an arbitrary (non-linear) global condition into a collection of local site constraints, and has been applied to massive distributed stream-monitoring tasks, achieving state-of-the-art performance. In this paper, we present a far more general geometric approach, based on the\n            <jats:italic>convex decomposition<\/jats:italic>\n            of an appropriate subset of the domain of the monitoring query, and formally prove that it is\n            <jats:italic>always<\/jats:italic>\n            guaranteed to perform at least as good as the covering spheres method. We analyze our approach and demonstrate its effectiveness for the important case of sketch-based approximate tracking for\n            <jats:italic>norm, range-aggregate, and join-aggregate queries<\/jats:italic>\n            , which have numerous applications in streaming data analysis. Experimental results on real-life data streams verify the superiority of our approach in practical settings, showing that it substantially outperforms the covering spheres method.\n          <\/jats:p>","DOI":"10.14778\/2735479.2735487","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"545-556","source":"Crossref","is-referenced-by-count":18,"title":["Monitoring distributed streams using convex decompositions"],"prefix":"10.14778","volume":"8","author":[{"given":"Arnon","family":"Lazerson","sequence":"first","affiliation":[{"name":"Israeli Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Izchak","family":"Sharfman","sequence":"additional","affiliation":[{"name":"Israeli Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Keren","sequence":"additional","affiliation":[{"name":"Haifa University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[{"name":"Israeli Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasilis","family":"Samoladas","sequence":"additional","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/tinyurl.com\/oh3xvp6. Technical report.  http:\/\/tinyurl.com\/oh3xvp6. Technical report."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.129"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.85"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366106"},{"key":"e_1_2_1_9_1","volume-title":"SODA","author":"Cormode G.","year":"2008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.16"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536220"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213867"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447920"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.24"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497461"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.102"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447923"},{"key":"e_1_2_1_20_1","volume-title":"VLDB '05","author":"Michel S.","year":"2005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497513"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292613"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989299"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.169"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559820"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735479.2735487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:19:59Z","timestamp":1672226399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735487"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735487","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}