{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T06:09:04Z","timestamp":1673330944900},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,6]]},"abstract":"Continuous aggregation queries over dynamic data are used for real time decision making and timely business intelligence. In this paper we consider queries where a client wants to be notified if the ratio of two aggregates over distributed data crosses a specified threshold. Consider these scenarios: a mechanism designed to defend against distributed denial of service attacks may be triggered when the fraction of packets arriving to a subnet is more than 5% of the total packets; or a distributed store chain withdraws its discount on luxury goods when sales of luxury goods constitute more than 20% of the overall sales. The challenge in executing such ratio threshold queries (RTQs) lies in incurring the minimal amount of communication necessary for propagation of updates from data sources to the aggregator node where the client query is executed. We address this challenge by proposing schemes for converting the client ratio threshold condition into conditions on individual distributed data sources. Whenever the condition associated with a source is violated, the source pushes its data values to the aggregator, which in turn pulls data values from other sources to determine whether the client threshold condition is indeed violated. We present algorithms to minimize the number of source condition violations (i.e., the number of pushes) while ensuring that no violation of the client threshold condition is missed. Further, in case of a source condition violation, we propose efficient selective pulling algorithms for intelligently choosing additional sources whose data should be pulled by the aggregator. Using performance evaluation on synthetic and real traces of data updates we show that our algorithms result in up to an order of magnitude less number of messages compared to existing approaches in the literature.<\/jats:p>","DOI":"10.14778\/2536354.2536357","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"565-576","source":"Crossref","is-referenced-by-count":5,"title":["Ratio threshold queries over distributed data sources"],"prefix":"10.14778","volume":"6","author":[{"given":"Rajeev","family":"Gupta","sequence":"first","affiliation":[{"name":"IBM Research, India"}]},{"given":"Krithi","family":"Ramamritham","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Mumbai, India"}]},{"given":"Mukesh","family":"Mohania","sequence":"additional","affiliation":[{"name":"IBM Research, India"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/872757.872764","volume-title":"SIGMOD '03: Proceedings of international conference on Management of data","author":"Babcock B.","year":"2003","unstructured":"B. Babcock and C. Olston . Distributed top-k monitoring . In SIGMOD '03: Proceedings of international conference on Management of data , pages 28 - 39 , 2003 . B. Babcock and C. Olston. Distributed top-k monitoring. In SIGMOD '03: Proceedings of international conference on Management of data, pages 28-39, 2003."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1109\/TKDE.2009.63","article-title":"Filtering data streams for entity-based continuous queries. In","author":"Cheng R.","year":"2010","unstructured":"R. Cheng , B. Kao , S. Prabhakar , A. Kwan , and Y. Tu . Filtering data streams for entity-based continuous queries. In IEEE Transactions on Knowledge and Data Engineering, pages 234 - 248 , 2010 . R. Cheng, B. Kao, S. Prabhakar, A. Kwan, and Y. Tu. Filtering data streams for entity-based continuous queries. In IEEE Transactions on Knowledge and Data Engineering, pages 234-248, 2010.","journal-title":"IEEE Transactions on Knowledge and Data Engineering, pages"},{"key":"e_1_2_1_3_1","volume-title":"WWW '05: Proceedings of the 14th international conference on World Wide Web","author":"Gupta R.","year":"2005","unstructured":"R. Gupta , A. Puri , and K. Ramamritham . Executing incoherency bounded continuous queries at web data aggregators . In WWW '05: Proceedings of the 14th international conference on World Wide Web , Chiba, Japan , 2005 . R. Gupta, A. Puri, and K. Ramamritham. Executing incoherency bounded continuous queries at web data aggregators. In WWW '05: Proceedings of the 14th international conference on World Wide Web, Chiba, Japan, 2005."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/1242572.1242616","volume-title":"WWW '07: Proceedings of the 16th international conference on World Wide Web","author":"Gupta R.","year":"2007","unstructured":"R. Gupta and K. Ramamritham . Optimized query planning of continuous aggregation queries in dynamic data dissemination networks . In WWW '07: Proceedings of the 16th international conference on World Wide Web , pages 321 - 330 , Banff, Alberta, Canada , 2007 . R. Gupta and K. Ramamritham. Optimized query planning of continuous aggregation queries in dynamic data dissemination networks. In WWW '07: Proceedings of the 16th international conference on World Wide Web, pages 321-330, Banff, Alberta, Canada, 2007."},{"key":"e_1_2_1_5_1","unstructured":"Investopedia. http:\/\/www.investopedia.com\/terms\/ l\/log-normal-distribution.asp. Investopedia. http:\/\/www.investopedia.com\/terms\/ l\/log-normal-distribution.asp."},{"key":"e_1_2_1_6_1","volume-title":"Network and Distributed System Security Symposium","author":"Ioannidis J.","year":"2002","unstructured":"J. Ioannidis and S. M. Bellovin . Implementing pushback: Router based defense against DDOS attacks . Network and Distributed System Security Symposium , 2002 . J. Ioannidis and S. M. Bellovin. Implementing pushback: Router based defense against DDOS attacks. Network and Distributed System Security Symposium, 2002."},{"key":"e_1_2_1_7_1","volume-title":"SIGCOMM workshop on Hot Topics in Networks (HotNets III)","author":"Jain A.","year":"2004","unstructured":"A. Jain , J. M. Hellerstein , S. Ratnasamy , and D. Wetherall . A wakeup call for internet monitoring systems: The case for distributed triggers . In SIGCOMM workshop on Hot Topics in Networks (HotNets III) , 2004 . A. Jain, J. M. Hellerstein, S. Ratnasamy, and D. Wetherall. A wakeup call for internet monitoring systems: The case for distributed triggers. In SIGCOMM workshop on Hot Topics in Networks (HotNets III), 2004."},{"key":"e_1_2_1_8_1","volume-title":"SIGMOD '06: Proceedings of international conference on Management of data","author":"Keralapura R.","year":"2006","unstructured":"R. Keralapura , G. Cormode , and J. Ramamritham . Communication efficient distributed monitoring of threshold counts . In SIGMOD '06: Proceedings of international conference on Management of data , 2006 . R. Keralapura, G. Cormode, and J. Ramamritham. Communication efficient distributed monitoring of threshold counts. In SIGMOD '06: Proceedings of international conference on Management of data, 2006."},{"key":"e_1_2_1_9_1","volume-title":"SIGMOD '03: Proceedings of international conference on Management of data","author":"Olston C.","year":"2003","unstructured":"C. Olston , J. Jiang , and J. Widom . Adaptive filters for continuous queries over distributed data streams . In SIGMOD '03: Proceedings of international conference on Management of data , San Diego , 2003 . C. Olston, J. Jiang, and J. Widom. Adaptive filters for continuous queries over distributed data streams. In SIGMOD '03: Proceedings of international conference on Management of data, San Diego, 2003."},{"key":"e_1_2_1_10_1","unstructured":"Technical report: Executing ratio threshold queries over distributed data sources. http:\/\/www.cse.iitb.ac.in\/~krithi\/papers\/rtq.pdf. Technical report: Executing ratio threshold queries over distributed data sources. http:\/\/www.cse.iitb.ac.in\/~krithi\/papers\/rtq.pdf."},{"key":"e_1_2_1_11_1","volume-title":"The caida backscatter-2004-2005 dataset - may 2004 - november","author":"Shannon C.","year":"2005","unstructured":"C. Shannon , D. Moore , E. Aben , and kc claffy. The caida backscatter-2004-2005 dataset - may 2004 - november 2005 . http:\/\/www.caida.org\/data\/ passive\/backscatter_2004_2005_dataset.x. C. Shannon, D. Moore, E. Aben, and kc claffy. The caida backscatter-2004-2005 dataset - may 2004 - november 2005. http:\/\/www.caida.org\/data\/ passive\/backscatter_2004_2005_dataset.x."},{"issue":"4","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/1292609.1292613","article-title":"A geometric approach to monitoring threshold functions over distributed data streams","volume":"32","author":"Sharfman I.","year":"2007","unstructured":"I. Sharfman , A. Schuster , and D. Keren . A geometric approach to monitoring threshold functions over distributed data streams . ACM Transactions of Database Systems , 32 ( 4 ): 23 , 2007 . I. Sharfman, A. Schuster, and D. Keren. A geometric approach to monitoring threshold functions over distributed data streams. ACM Transactions of Database Systems, 32(4):23, 2007.","journal-title":"ACM Transactions of Database Systems"},{"key":"e_1_2_1_13_1","volume-title":"VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases","author":"Zhu S.","year":"2004","unstructured":"S. Zhu and C. V. Ravishankar . Stochastic consistency, and scalable pull-based caching for erratic data stream sources . In VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases , 2004 . S. Zhu and C. V. Ravishankar. Stochastic consistency, and scalable pull-based caching for erratic data stream sources. In VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases, 2004."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536354.2536357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:07:34Z","timestamp":1672222054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536354.2536357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":13,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.14778\/2536354.2536357"],"URL":"https:\/\/doi.org\/10.14778\/2536354.2536357","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}