{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T07:23:35Z","timestamp":1763018615956},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3611479.3611521","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"3227-3239","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions"],"prefix":"10.14778","volume":"16","author":[{"given":"Kanat","family":"Tangwongsan","sequence":"first","affiliation":[{"name":"Mahidol University International College"}]},{"given":"Martin","family":"Hirzel","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Scott","family":"Schneider","sequence":"additional","affiliation":[{"name":"Meta"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2022","unstructured":"2022. Citi Bike System Data. https:\/\/www.citibikenyc.com\/system-data . Retrieved December , 2022 . 2022. Citi Bike System Data. https:\/\/www.citibikenyc.com\/system-data. Retrieved December, 2022."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536229"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.42"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3054898"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2335484.2335513"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322127"},{"key":"e_1_2_1_9_1","first-page":"28","article-title":"Apache Flink: Stream and Batch Processing in a Single Engine","volume":"36","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone , Asterios Katsifodimos , Stephan Ewen , Volker Markl , Seif Haridi , and Kostas Tzoumas . 2015 . Apache Flink: Stream and Batch Processing in a Single Engine . Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36 , 4 (2015), 28 -- 38 . http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink: Stream and Batch Processing in a Single Engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36, 4 (2015), 28--38. http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf","journal-title":"Bulletin of the IEEE Computer Society Technical Committee on Data Engineering"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas","unstructured":"Thomas Cormen , Charles Leiserson , and Ronald Rivest . 1990. Introduction to Algorithms . MIT Press . Thomas Cormen, Charles Leiserson, and Ronald Rivest. 1990. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039207"},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Machine Learning (ICML). 648--656","author":"Izbicki Michael","year":"2013","unstructured":"Michael Izbicki . 2013 . Algebraic Classifiers: A Generic Approach to Fast Cross-Validation, Online Training, and Parallel Training . In International Conference on Machine Learning (ICML). 648--656 . http:\/\/proceedings.mlr.press\/v28\/izbicki13.html Michael Izbicki. 2013. Algebraic Classifiers: A Generic Approach to Fast Cross-Validation, Online Training, and Parallel Training. In International Conference on Machine Learning (ICML). 648--656. http:\/\/proceedings.mlr.press\/v28\/izbicki13.html"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225090"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807290"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34175-6_13"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453890"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452785"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342357"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085509"},{"key":"e_1_2_1_22_1","volume-title":"Optimal and General Out-of-Order Sliding-Window Aggregation. In Conference on Very Large Data Bases (VLDB). 1167--1180","author":"Tangwongsan Kanat","year":"2019","unstructured":"Kanat Tangwongsan , Martin Hirzel , and Scott Schneider . 2019 . Optimal and General Out-of-Order Sliding-Window Aggregation. In Conference on Very Large Data Bases (VLDB). 1167--1180 . http:\/\/www.vldb.org\/pvldb\/vol12\/p1167-tangwongsan.pdf Kanat Tangwongsan, Martin Hirzel, and Scott Schneider. 2019. Optimal and General Out-of-Order Sliding-Window Aggregation. In Conference on Very Large Data Bases (VLDB). 1167--1180. http:\/\/www.vldb.org\/pvldb\/vol12\/p1167-tangwongsan.pdf"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00668-3"},{"key":"e_1_2_1_24_1","unstructured":"Kanat Tangwongsan Martin Hirzel and Scott Schneider. 2023. Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions (Extended Version). https:\/\/arxiv.org\/abs\/2307.11210.  Kanat Tangwongsan Martin Hirzel and Scott Schneider. 2023. Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions (Extended Version). https:\/\/arxiv.org\/abs\/2307.11210."},{"key":"e_1_2_1_25_1","volume-title":"Hammer Slide: Work- and CPU-efficient Streaming Window Aggregation. In Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 34--41","author":"Theodorakis Georgios","year":"2018","unstructured":"Georgios Theodorakis , Alexandros Koliousis , Peter R. Pietzuch , and Holger Pirk . 2018 . Hammer Slide: Work- and CPU-efficient Streaming Window Aggregation. In Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 34--41 . http:\/\/adms-conf.org\/2018-camera-ready\/SIMDWindowPaper_ADMS'18.pdf Georgios Theodorakis, Alexandros Koliousis, Peter R. Pietzuch, and Holger Pirk. 2018. Hammer Slide: Work- and CPU-efficient Streaming Window Aggregation. In Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 34--41. http:\/\/adms-conf.org\/2018-camera-ready\/SIMDWindowPaper_ADMS'18.pdf"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389753"},{"key":"e_1_2_1_27_1","volume-title":"Conference on Extending Database Technology (EDBT). 435--438","author":"Theodorakis Georgios","year":"2020","unstructured":"Georgios Theodorakis , Peter R. Pietzuch , and Holger Pirk . 2020 . SlideSide: A fast Incremental Stream Processing Algorithm for Multiple Queries . In Conference on Extending Database Technology (EDBT). 435--438 . https:\/\/openproceedings.org\/2020\/conf\/edbt\/paper_337.pdf Georgios Theodorakis, Peter R. Pietzuch, and Holger Pirk. 2020. SlideSide: A fast Incremental Stream Processing Algorithm for Multiple Queries. In Conference on Extending Database Technology (EDBT). 435--438. https:\/\/openproceedings.org\/2020\/conf\/edbt\/paper_337.pdf"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2019.10"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2868960"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:18:51Z","timestamp":1695507531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":29,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611521"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611521","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}