I can parse you: Grammars for dialogs
Martin Hirzel, Louis Mandel, et al.
SNAPL 2017
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.
Martin Hirzel, Louis Mandel, et al.
SNAPL 2017
Martin Hirzel, Johannes Henkel, et al.
ACM SIGPLAN Notices
Guillaume Baudart, Javier Burroni, et al.
PLDI 2021
Nikitha Rao, Jason Tsay, et al.
MSR 2022