TY - GEN
T1 - Competitive cost-savings in data stream management systems
AU - Chung, Christine
AU - Guirguis, Shenoda
AU - Kurdia, Anastasia
PY - 2014
Y1 - 2014
N2 - In Continuous Data Analytics and in monitoring applications, hundreds of similar Aggregate Continuous Queries (ACQs) are registered at the Data Stream Management System (DSMS) to continuously monitor the infinite input stream of data tuples. Optimizing the processing of these ACQs is crucial in order for the DSMS to operate at the adequate required scalability. One optimization technique is to share the results of partial aggregation operations between different ACQs on the same data stream. However, finding the query execution plan that attains maximum reduction in total plan cost is computationally expensive. Weave Share, a multiple ACQs optimizer that computes query plans in a greedy fashion, was recently shown in experiments to achieve more than an order of magnitude improvement over the best existing alternatives. Maximizing the benefit of sharing, i.e., maximizing the cost-savings achieved by sharing partial aggregation results, is the goal of Weave Share. In this paper we prove that Weave Share approximates the optimal cost-savings to within a factor of 4 for a practical variant of the problem. To the best of our knowledge, this is the first theoretical guarantee provided for this problem. We also provide exact solutions for two natural special cases.
AB - In Continuous Data Analytics and in monitoring applications, hundreds of similar Aggregate Continuous Queries (ACQs) are registered at the Data Stream Management System (DSMS) to continuously monitor the infinite input stream of data tuples. Optimizing the processing of these ACQs is crucial in order for the DSMS to operate at the adequate required scalability. One optimization technique is to share the results of partial aggregation operations between different ACQs on the same data stream. However, finding the query execution plan that attains maximum reduction in total plan cost is computationally expensive. Weave Share, a multiple ACQs optimizer that computes query plans in a greedy fashion, was recently shown in experiments to achieve more than an order of magnitude improvement over the best existing alternatives. Maximizing the benefit of sharing, i.e., maximizing the cost-savings achieved by sharing partial aggregation results, is the goal of Weave Share. In this paper we prove that Weave Share approximates the optimal cost-savings to within a factor of 4 for a practical variant of the problem. To the best of our knowledge, this is the first theoretical guarantee provided for this problem. We also provide exact solutions for two natural special cases.
UR - http://www.scopus.com/inward/record.url?scp=84904727404&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904727404&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08783-2_12
DO - 10.1007/978-3-319-08783-2_12
M3 - Conference contribution
AN - SCOPUS:84904727404
SN - 9783319087825
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 129
EP - 140
BT - Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PB - Springer Verlag
T2 - 20th International Computing and Combinatorics Conference, COCOON 2014
Y2 - 4 August 2014 through 6 August 2014
ER -