Welcome to the ADMT Publication Server

FlatFIT, Aggregate Continuous Query, Sliding-Window Processing

DocUID: 2017-005

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

Abstract: Data stream processing is becoming essential in most current advanced scientific or business applications as data production rates are increasing. Different companies compete to efficiently ingest high velocity data and apply some form of computation in order to make better business decisions. In order to successfully compete in this environment, companies are focusing on the most recent data within a count or time-based window by continuously executing aggregate queries on it. Incremental sliding-window computation is commonly used to avoid the performance implications of re-evaluating the aggregate value of the window from scratch on every update. The state-of-the-art FlatFAT technique executes ACQs with high efficiency, but it does not scale well with the increasing workloads. In this paper we propose a novel algorithm, FlatFIT, that accelerates such calculations by intelligently maintaining index structures, leading to higher reuse of intermediate calculations and thus exceptional scalability in systems with heavy workloads. Our theoretical analysis shows that FlatFIT is superior in both time and space complexities compared to FlatFAT, while maintaining the same query generality. Given a window of size n, FlatFIT achieves constant algorithmic complexity compared to O(log(n)) complexity of FlatFAT. We experimentally show that FlatFIT achieves up to a 17x throughput improvement over FlatFAT for the same input workload while using less memory.

Published In: 29th International Conference on Scientific and Statistical Database Management

Year Published: 2017

Project: AQSIOS Subject Area: Query Processing, Data Streams

Publication Type: Conference Paper

Sponsor: Others

Citation:Text Latex BibTex XML Anatoli U. Shein, Panos K. Chrysanthis, and Alexandros Labrinidis. FlatFIT, Aggregate Continuous Query, Sliding-Window Processing. 29th International Conference on Scientific and Statistical Database Management. 2017.