Publication: General incremental sliding-window aggregation
Issued Date
2015-01-01
Resource Type
ISSN
21508097
Other identifier(s)
2-s2.0-85013685244
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Proceedings of the VLDB Endowment. Vol.8, No.7 (2015), 702-713
Suggested Citation
Kanat Tangwongsan, Martin Hirzel, Scott Schneider, Kun Lung Wu General incremental sliding-window aggregation. Proceedings of the VLDB Endowment. Vol.8, No.7 (2015), 702-713. doi:10.14778/2752939.2752940 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/35834
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
General incremental sliding-window aggregation
Other Contributor(s)
Abstract
© 2015 VLDB Endowment 21508097/15/03. Stream processing is gaining importance as more data becomes available in the form of continuous streams and companies compete to promptly extract insights from them. In such applications, sliding-window aggregation is a central operator, and incremental aggregation helps avoid the performance penalty of re-aggregating from scratch for each window change. This paper presents Reactive Aggregator (RA), a new framework for incremental sliding-window aggregation. RA is general in that it does not require aggregation functions to be invertible or commutative, and it does not require windows to be FIFO. We implemented RA as a drop-in replacement for the Aggregate operator of a commercial streaming engine. Given m updates on a window of size n, RA has an algorithmic complexity of O(m + m log(n/m)), rivaling the best prior algorithms for any m. Furthermore, RA's implementation minimizes overheads from allocation and pointer traversals by using a single flat array.