{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T05:23:37Z","timestamp":1778390617911,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>\n            Sliding-window aggregation derives a user-defined summary of the most-recent portion of a data stream. For in-order streams, each window change can be handled in\n            <jats:italic>O<\/jats:italic>\n            (1) time even when the aggregation operator is not invertible. But streaming data often arrive inherently out-of-order, e.g., due to clock drifts and communication delays. For such streams, prior work resorted to latency-prone buffering or spent\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time for every window change, where n is the instantaneous window size. This paper presents FiBA, a novel real-time sliding window aggregation algorithm that optimally handles streams of varying degrees of out-of-orderness. FiBA is as general as the state-of-the-art and supports variable-sized windows. An insert or evict takes amortized\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>d<\/jats:italic>\n            ) time, where\n            <jats:italic>d<\/jats:italic>\n            is the distance of the change to the window's boundary. This means\n            <jats:italic>O<\/jats:italic>\n            (1) time for in-order arrivals and nearly\n            <jats:italic>O<\/jats:italic>\n            (1) time for slightly out-of-order arrivals, tending to\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time for the most severely out-of-order arrivals. We also prove a matching lower bound, showing optimality. At its heart, the algorithm combines and extends finger searching, lazy rebalancing, and position-aware partial aggregates. Further, FiBA can answer range queries that aggregate subwindows for window sharing. Finally, our experiments show that FiBA performs well in practice and conforms to the theoretical findings, with significantly higher throughput than\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) algorithms.\n          <\/jats:p>","DOI":"10.14778\/3339490.3339499","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1167-1180","source":"Crossref","is-referenced-by-count":27,"title":["Optimal and general out-of-order sliding-window aggregation"],"prefix":"10.14778","volume":"12","author":[{"given":"Kanat","family":"Tangwongsan","sequence":"first","affiliation":[{"name":"Mahidol University International College"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hirzel","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott","family":"Schneider","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/www.citibikenyc.com\/system-data","author":"System Data Citi Bike","year":"2019","unstructured":"Citi Bike System Data . https:\/\/www.citibikenyc.com\/system-data , 2019 . Retrieved April, 2019. Citi Bike System Data. https:\/\/www.citibikenyc.com\/system-data, 2019. Retrieved April, 2019."},{"key":"e_1_2_1_2_1","first-page":"277","volume-title":"Conference on Innovative Data Systems Research (CIDR)","author":"Abadi D. J.","year":"2005","unstructured":"D. J. Abadi , Y. Ahmad , M. Balazinska , U. Cetintemel , M. Cherniack , J.-H. Hwang , W. Lindner , A. S. Maskey , A. Rasin , E. Ryvkina , N. Tatbul , Y. Xing , and S. Zdonik . The design of the Borealis stream processing engine . In Conference on Innovative Data Systems Research (CIDR) , pages 277 -- 289 , 2005 . D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The design of the Borealis stream processing engine. In Conference on Innovative Data Systems Research (CIDR), pages 277--289, 2005."},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","year":"2018","unstructured":"adamax. Re : Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations. http:\/\/stackoverflow.com\/questions\/4802038\/, 2011 . Retrieved Oct. , 2018 . adamax. Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations. http:\/\/stackoverflow.com\/questions\/4802038\/, 2011. Retrieved Oct., 2018."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536229"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824076"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687590"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316720"},{"key":"e_1_2_1_9_1","first-page":"363","volume-title":"Conference on Innovative Data Systems Research (CIDR)","author":"Barga R. S.","year":"2007","unstructured":"R. S. Barga , J. Goldstein , M. Ali , and M. Hong . Consistent streaming through time: A vision for event stream processing . In Conference on Innovative Data Systems Research (CIDR) , pages 363 -- 373 , 2007 . R. S. Barga, J. Goldstein, M. Ali, and M. Hong. Consistent streaming through time: A vision for event stream processing. In Conference on Innovative Data Systems Research (CIDR), pages 363--373, 2007."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733016"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1385989.1386023"},{"issue":"4","key":"e_1_2_1_14_1","first-page":"28","article-title":"Apache Flink: Stream and batch processing in a single engine","volume":"38","author":"Carbone P.","year":"2015","unstructured":"P. Carbone , A. Katsifodimos , S. Ewen , V. Markl , S. Haridi , and K. Tzoumas . Apache Flink: Stream and batch processing in a single engine . IEEE Data Engineering Bulletin , 38 ( 4 ): 28 -- 38 , 2015 . P. Carbone, A. Katsifodimos, S. Ewen, V. Markl, S. Haridi, and K. Tzoumas. Apache Flink: Stream and batch processing in a single engine. IEEE Data Engineering Bulletin, 38(4):28--38, 2015.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983807"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00067"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920873"},{"key":"e_1_2_1_18_1","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"1990","unstructured":"T. Cormen , C. Leiserson , and R. Rivest . Introduction to Algorithms . MIT Press , 1990 . T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803395"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"e_1_2_1_22_1","first-page":"648","volume-title":"International Conference on Machine Learning (ICML)","author":"Izbicki M.","year":"2013","unstructured":"M. Izbicki . Algebraic classifiers : A generic approach to fast cross-validation, online training, and parallel training . In International Conference on Machine Learning (ICML) , pages 648 -- 656 , 2013 . M. Izbicki. Algebraic classifiers: A generic approach to fast cross-validation, online training, and parallel training. In International Conference on Machine Learning (ICML), pages 648--656, 2013."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2675743.2771828"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732953"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807290"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142543"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058150.1058158"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453890"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085509"},{"key":"e_1_2_1_30_1","first-page":"397","volume-title":"Conference on Extending Database Technology (EDBT)","author":"Shein A. U.","year":"2018","unstructured":"A. U. Shein , P. K. Chrysanthis , and A. Labrinidis . SlickDeque: High throughput and low latency incremental sliding-window aggregation . In Conference on Extending Database Technology (EDBT) , pages 397 -- 408 , 2018 . A. U. Shein, P. K. Chrysanthis, and A. Labrinidis. SlickDeque: High throughput and low latency incremental sliding-window aggregation. In Conference on Extending Database Technology (EDBT), pages 397--408, 2018."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055596"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093742.3093925"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752940"},{"key":"e_1_2_1_34_1","volume-title":"Poster at the International Conference on Data Engineering (ICDE-Poster)","author":"Traub J.","year":"2018","unstructured":"J. Traub , P. Grulich , A. R. Cuellar , S. Bres , A. Katsifodimos , T. Rabl , and V. Markl . Scotty: Efficient window aggregation for out-of-order stream processing . In Poster at the International Conference on Data Engineering (ICDE-Poster) , 2018 . J. Traub, P. Grulich, A. R. Cuellar, S. Bres, A. Katsifodimos, T. Rabl, and V. Markl. Scotty: Efficient window aggregation for out-of-order stream processing. In Poster at the International Conference on Data Engineering (ICDE-Poster), 2018."},{"key":"e_1_2_1_35_1","volume-title":"Conference on Extending Database Technology (EDBT)","author":"Traub J.","year":"2019","unstructured":"J. Traub , P. M. Grulich , A. R. Cu\u00e9llar , S. Bre\u00df , A. Katsifodimos , T. Rabl , and V. Markl . Efficient window aggregation with general stream slicing . In Conference on Extending Database Technology (EDBT) , 2019 . J. Traub, P. M. Grulich, A. R. Cu\u00e9llar, S. Bre\u00df, A. Katsifodimos, T. Rabl, and V. Markl. Efficient window aggregation with general stream slicing. In Conference on Extending Database Technology (EDBT), 2019."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:26:44Z","timestamp":1672223204000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339499"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339499","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}