  Sliding-window aggregation is a foundational stream processing primitive that
efficiently summarizes recent data. The state-of-the-art algorithms for
sliding-window aggregation are highly efficient when stream data items are
evicted or inserted one at a time, even when some of the insertions occur
out-of-order. However, real-world streams are often not only out-of-order but
also burtsy, causing data items to be evicted or inserted in larger bulks. This
paper introduces a new algorithm for sliding-window aggregation with bulk
eviction and bulk insertion. For the special case of single insert and evict,
our algorithm matches the theoretical complexity of the best previous
out-of-order algorithms. For the case of bulk evict, our algorithm improves
upon the theoretical complexity of the best previous algorithm for that case
and also outperforms it in practice. For the case of bulk insert, there are no
prior algorithms, and our algorithm improves upon the naive approach of
emulating bulk insert with a loop over single inserts, both in theory and in
practice. Overall, this paper makes high-performance algorithms for sliding
window aggregation more broadly applicable by efficiently handling the
ubiquitous cases of out-of-order data and bursts.
