{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T02:53:34Z","timestamp":1723172014909},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2007,11]]},"abstract":"Monitoring data streams in a distributed system is the focus of much research in recent years. Most of the proposed schemes, however, deal with monitoring simple aggregated values, such as the frequency of appearance of items in the streams. More involved challenges, such as the important task of feature selection (e.g., by monitoring the information gain of various features), still require very high communication overhead using naive, centralized algorithms.<\/jats:p>\n We present a novel geometric approach which reduces monitoring the value of a function (vis-\u00e0-vis a threshold) to a set of constraints applied locally on each of the streams. The constraints are used to locally filter out data increments that do not affect the monitoring outcome, thus avoiding unnecessary communication. As a result, our approach enables monitoring of arbitrary threshold functions over distributed data streams in an efficient manner.<\/jats:p>\n We present experimental results on real-world data which demonstrate that our algorithms are highly scalable, and considerably reduce communication load in comparison to centralized algorithms.<\/jats:p>","DOI":"10.1145\/1292609.1292613","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"23","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":78,"title":["A geometric approach to monitoring threshold functions over distributed data streams"],"prefix":"10.1145","volume":"32","author":[{"given":"Izchak","family":"Sharfman","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Daniel","family":"Keren","sequence":"additional","affiliation":[{"name":"Haifa University, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"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.1145\/603867.603884"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Berkovitz L. 2002. Convexity and Optimization in Rn. Wiley New York NY. Berkovitz L. 2002. Convexity and Optimization in R n . Wiley New York NY.","DOI":"10.1002\/047124970X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.170"},{"key":"e_1_2_1_8_1","volume-title":"VLDB '02: Proceedings of the International Conference on Very Large Data Bases. 215--226","author":"Carney D."},{"key":"e_1_2_1_9_1","volume-title":"ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming","author":"Charikar M."},{"key":"e_1_2_1_10_1","volume-title":"CIDR 2003: Proceedings of the First Biennial Conference on Innovative Data Systems Research","author":"Cherniack M."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_12_1","volume-title":"INFOCOM '01: Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. 1012--1019","author":"Dilman M."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564880"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162678.1162684"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 3rd ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets","author":"Jain A."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005345"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.790816"},{"key":"e_1_2_1_22_1","volume-title":"ICDE '02: Proceedings of the 18th International Conference on Data Engineering (ICDE'02)","author":"Madden S."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564698"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1053724.1054115"},{"key":"e_1_2_1_25_1","volume-title":"VLDB '02: Proceedings of the International Conference on Very Large Data Bases. 346--357","author":"Manku G. S."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872855"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Third International Conference on Language Resources and Evaluation (Las Palmas de Gran Canaria).","author":"Rose T."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016376116653"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.387489"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130333"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057464"},{"key":"e_1_2_1_35_1","volume-title":"ICDE '00: Proceedings of the 16th International Conference on Data Engineering. IEEE Computer Society","author":"Yi B.-K."},{"key":"e_1_2_1_36_1","volume-title":"VLDB '02: Proceedings of the International Conference on Very Large Data Bases. 358--369","author":"Zhu Y."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1292609.1292613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:40:14Z","timestamp":1672256414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1292609.1292613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1292609.1292613"],"URL":"https:\/\/doi.org\/10.1145\/1292609.1292613","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}