Welcome to the ADMT Publication Server

F1: Accelerating the optimization of Aggregate Continuous Queries

DocUID: 2015-005 Full Text: PDF

Author: Anatoli U. Shein, Panos K. Chrysanthis, Alexandros Labrinidis

Abstract: Data Stream Management Systems performing on-line analytics rely on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). The state-of-the-art WeaveShare optimizer uses the Weavability concept in order to selectively combine ACQs for partial aggregation and produce high quality execution plans. However, WeaveShare does not scale well with the number of ACQs. In this paper we propose a novel closed formula, F1, that accelerates Weavability calculations, and thus allows WeaveShare to achieve exceptional scalability in systems with heavy workloads. In general, F1 can reduce the computation time of any technique that combines partial aggregations within composite slides of multiple ACQs. We theoretically analyze the Bit Set approach currently used by WeaveShare and show that F1 is superior in both time and space complexities. We show that F 1 performs ∼ 10^62 times less operations compared to Bit Set to produce the same execution plan for the same input. We experimentally show that F1 executes up to 60,000 times faster and can handle 1,000,000 ACQs in a setting where the limit for the current technique is 550.

Published In: Proceedings of the 24th ACM International Conference on Information and Knowledge Management

Place Published: Melbourne, Australia

Year Published: 2015

Project: AQSIOS Subject Area: Data Streams

Publication Type: Conference Paper

Sponsor: NSF CBET-1250171

Citation:Text Latex BibTex XML Anatoli U. Shein, Panos K. Chrysanthis, and Alexandros Labrinidis. F1: Accelerating the optimization of Aggregate Continuous Queries. Proceedings of the 24th ACM International Conference on Information and Knowledge Management. 2015. Melbourne, Australia.