Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions
Issued Date
2023-01-01
Resource Type
eISSN
21508097
Scopus ID
2-s2.0-85171844169
Journal Title
Proceedings of the VLDB Endowment
Volume
16
Issue
11
Start Page
3227
End Page
3239
Rights Holder(s)
SCOPUS
Bibliographic Citation
Proceedings of the VLDB Endowment Vol.16 No.11 (2023) , 3227-3239
Suggested Citation
Tangwongsan K., Hirzel M., Schneider S. Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions. Proceedings of the VLDB Endowment Vol.16 No.11 (2023) , 3227-3239. 3239. doi:10.14778/3611479.3611521 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/90259
Title
Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions
Author(s)
Author's Affiliation
Other Contributor(s)
Abstract
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 bursty, 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.