SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation
DocUID: 2018-002 Full Text:
PDF Author: Anatoli U. Shein, Panos K. Chrysanthis, Alexandros Labrinidis
Abstract: Online analytics, in most advanced scientific and business applications, rely heavily on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). Incremental slidingwindow computation is used in the state-of-the-art ACQ processing algorithms (FlatFIT, TwoStacks, and DABA) to avoid the reevaluation of the aggregate value of the window from scratch on every update. FlatFIT and TwoStacks aim to increase throughput, and DABA to minimize latency, while all process invertible and non-invertible aggregates uniformly. In this paper, we propose a novel algorithm, SlickDeque, that distinguishes the execution between invertible and non-invertible aggregates and offers better throughput and latency for both types. In addition, our method requires less memory and efficiently supports multi-ACQ processing. We theoretically show the time and space complexity advantages of SlickDeque and experimentally validate them using a real workload. Specifically, our approach maintains 283% lower latency spikes on average while achieving up to 19% throughput improvement in a single query environment and up to 345% improvement in amulti-query environment over the state-of-the-art approaches along with requiring up to 5 times less memory.
Published In: 21st International Conference on Extending Database Technology
Pages: 397-408
Year Published: 2018
Project: Others, CausalMGM Subject Area: Biomedical Informatics, Data Streams
Publication Type: Conference Paper
Sponsor: NIH U01HL137159, Others