Competitive cost-savings in data stream management systems

Christine Chung*, Shenoda Guirguis, Anastasia Kurdia

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Pages129-140
Number of pages12
ISBN (Print)9783319087825
DOIs
StatePublished - 2014
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: Aug 4 2014Aug 6 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Computing and Combinatorics Conference, COCOON 2014
Country/TerritoryUnited States
CityAtlanta, GA
Period8/4/148/6/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Competitive cost-savings in data stream management systems'. Together they form a unique fingerprint.

Cite this