Processing complex aggregate queries over data streams Export

@inproceedings{Dobra2002, abstract = {Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed.In this paper, we consider the problem of approximately answering general aggregate SQL queries over continuous data streams with limited memory. Our method relies on randomizing techniques that compute small "sketch" summaries of the streams that can then be used to provide approximate answers to aggregate queries with provable guarantees on the approximation error. We also demonstrate how existing statistical information on the base data (e.g., histograms) can be used in the proposed framework to improve the quality of the approximation provided by our algorithms. The key idea is to intelligently partition the domain of the underlying attribute(s) and, thus, decompose the sketching problem in a way that provably tightens our guarantees. Results of our experimental study with real-life as well as synthetic data streams indicate that sketches provide significantly more accurate answers compared to histograms for aggregate queries. This is especially true when our domain partitioning methods are employed to further boast the accuracy of the final estimates.}, address = {New York, NY, USA}, author = {Dobra, Alin and Garofalakis, Minos and Gehrke, Johannes and Rastogi, Rajeev}, booktitle = {SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data}, citeulike-article-id = {2206652}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=564699}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/564691.564699}, doi = {10.1145/564691.564699}, isbn = {1-58113-497-5}, keywords = {qoi, statistics}, location = {Madison, Wisconsin}, pages = {61--72}, posted-at = {2009-08-11 07:04:22}, priority = {2}, publisher = {ACM}, title = {Processing complex aggregate queries over data streams}, url = {http://dx.doi.org/10.1145/564691.564699}, year = {2002} }

TY - CONF ID - Dobra2002 L3 - citeulike-article-id:2206652 N2 - Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed.In this paper, we consider the problem of approximately answering general aggregate SQL queries over continuous data streams with limited memory. Our method relies on randomizing techniques that compute small "sketch" summaries of the streams that can then be used to provide approximate answers to aggregate queries with provable guarantees on the approximation error. We also demonstrate how existing statistical information on the base data (e.g., histograms) can be used in the proposed framework to improve the quality of the approximation provided by our algorithms. The key idea is to intelligently partition the domain of the underlying attribute(s) and, thus, decompose the sketching problem in a way that provably tightens our guarantees. Results of our experimental study with real-life as well as synthetic data streams indicate that sketches provide significantly more accurate answers compared to histograms for aggregate queries. This is especially true when our domain partitioning methods are employed to further boast the accuracy of the final estimates. CY - Madison, Wisconsin SN - 1-58113-497-5 AD - New York, NY, USA EP - 72 TI - Processing complex aggregate queries over data streams PB - ACM T2 - SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data SP - 61 KW - qoi KW - statistics AU - Dobra, Alin AU - Garofalakis, Minos AU - Gehrke, Johannes AU - Rastogi, Rajeev PY - 2002/// UR - http://dx.doi.org/10.1145/564691.564699 ER -