{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T02:16:17Z","timestamp":1769912177225,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>m<\/jats:italic>\n            updates on a window of size\n            <jats:italic>n<\/jats:italic>\n            , RA has an algorithmic complexity of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            log (\n            <jats:italic>n\/m<\/jats:italic>\n            )), rivaling the best prior algorithms for any\n            <jats:italic>m<\/jats:italic>\n            . Furthermore, RA's implementation minimizes overheads from allocation and pointer traversals by using a single flat array.\n          <\/jats:p>","DOI":"10.14778\/2752939.2752940","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"702-713","source":"Crossref","is-referenced-by-count":89,"title":["General incremental sliding-window aggregation"],"prefix":"10.14778","volume":"8","author":[{"given":"Kanat","family":"Tangwongsan","sequence":"first","affiliation":[{"name":"Mahidol University International College"}]},{"given":"Martin","family":"Hirzel","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}]},{"given":"Scott","family":"Schneider","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}]},{"given":"Kun-Lung","family":"Wu","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}]}],"member":"320","published-online":{"date-parts":[[2015,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596527.1596530"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536229"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316720"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038923"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920874"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260801"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567544"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(82)90020-0"},{"key":"e_1_2_1_12_1","volume-title":"Generic windowing support for extensible stream processing systems. Software Practice and Experience (SP&E), 44(9): 1105--1128","author":"Gedik B.","year":"2014","unstructured":"B. Gedik . Generic windowing support for extensible stream processing systems. Software Practice and Experience (SP&E), 44(9): 1105--1128 , 2014 . B. Gedik. Generic windowing support for extensible stream processing systems. Software Practice and Experience (SP&E), 44(9): 1105--1128, 2014."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655593"},{"key":"e_1_2_1_15_1","volume-title":"Operating Systems Design and Implementation (OSDI)","author":"Gunda P. K.","year":"2010","unstructured":"P. K. Gunda , L. Ravindranath , C. A. Thekkath , Y. Yu , and L. Zhuang . Nectar: Automatic management of data and computation in datacenters . In Operating Systems Design and Implementation (OSDI) , 2010 . P. K. Gunda, L. Ravindranath, C. A. Thekkath, Y. Yu, and L. Zhuang. Nectar: Automatic management of data and computation in datacenters. In Operating Systems Design and Implementation (OSDI), 2010."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2335484.2335506"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1147\/JRD.2013.2243535"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44833-4_6"},{"key":"e_1_2_1_20_1","volume-title":"IBM InfoSphere Streams","unstructured":"IBMInfoSphereStreams. IBM InfoSphere Streams . http:\/\/www.ibm.com\/software\/data\/infosphere\/streams\/. Accessed: 2014-08-27. IBMInfoSphereStreams. IBM InfoSphere Streams. http:\/\/www.ibm.com\/software\/data\/infosphere\/streams\/. Accessed: 2014-08-27."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454179"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142543"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058150.1058158"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807138"},{"key":"e_1_2_1_25_1","volume-title":"Conference on Innovative Data Systems Research (CIDR)","author":"McSherry F.","year":"2013","unstructured":"F. McSherry , D. G. Murray , R. Isaacs , and M. Isard . Differential dataflow . In Conference on Innovative Data Systems Research (CIDR) , 2013 . F. McSherry, D. G. Murray, R. Isaacs, and M. Isard. Differential dataflow. In Conference on Innovative Data Systems Research (CIDR), 2013."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847360"},{"key":"e_1_2_1_27_1","first-page":"251","volume-title":"Operating Systems Design and Implementation (OSDI)","author":"Peng D.","year":"2010","unstructured":"D. Peng and F. Dabek . Large-scale incremental processing using distributed transactions and notifications . In Operating Systems Design and Implementation (OSDI) , pages 251 -- 264 , 2010 . D. Peng and F. Dabek. Large-scale incremental processing using distributed transactions and notifications. In Operating Systems Design and Implementation (OSDI), pages 251--264, 2010."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370826"},{"key":"e_1_2_1_30_1","volume-title":"Data Structures, Sorting, Searching (3. ed.)","author":"Sedgewick R.","year":"1999","unstructured":"R. Sedgewick . Algorithms in C++ - Parts 1--4 : Fundamentals , Data Structures, Sorting, Searching (3. ed.) . Addison-Wesley-Longman , 1999 . R. Sedgewick. Algorithms in C++ - Parts 1--4: Fundamentals, Data Structures, Sorting, Searching (3. ed.). Addison-Wesley-Longman, 1999."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367513"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/645901.672773"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-36477-3_21","volume-title":"Computer Science in Perspective, Essays Dedicated to Thomas Ottmann","author":"Soisalon-Soininen E.","year":"2003","unstructured":"E. Soisalon-Soininen and P. Widmayer . Single and bulk updates in stratified trees: An amortized and worst-case analysis . In Computer Science in Perspective, Essays Dedicated to Thomas Ottmann , pages 278 -- 292 , 2003 . E. Soisalon-Soininen and P. Widmayer. Single and bulk updates in stratified trees: An amortized and worst-case analysis. In Computer Science in Perspective, Essays Dedicated to Thomas Ottmann, pages 278--292, 2003."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595641"},{"key":"e_1_2_1_35_1","first-page":"1113","volume-title":"Demonstration at Very Large Data Bases (VLDB-Demo)","author":"Wang H.","year":"2003","unstructured":"H. Wang , C. Zaniolo , and C. R. Luo . ATLAS: A small but complete SQL extension for data mining and data streams . In Demonstration at Very Large Data Bases (VLDB-Demo) , pages 1113 -- 1116 , 2003 . H. Wang, C. Zaniolo, and C. R. Luo. ATLAS: A small but complete SQL extension for data mining and data streams. In Demonstration at Very Large Data Bases (VLDB-Demo), pages 1113--1116, 2003."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656393"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629600"},{"key":"e_1_2_1_38_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\/2752939.2752940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:55Z","timestamp":1672222495000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2752939.2752940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":37,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.14778\/2752939.2752940"],"URL":"https:\/\/doi.org\/10.14778\/2752939.2752940","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}